Kalit so'zlari: Chiziqli qidiruv usuli, Binar qidiruv usuli, Interpolyatsiya algoritmi
Download 372.57 Kb.
|
2-ma'ruza
|
2-ma'ruza matni Kalit so'zlari: Chiziqli qidiruv usuli, Binar qidiruv usuli, Interpolyatsiya algoritmi 1. Chiziqli qidiruv algoritmi Bu qidiruv algoritmining asosiy g’oyasi – massivning barcha elementlarini qidirilayotgan kalit-qiymat bilan ketma-ket taqqoslab chiqish va topilgan elementning joylashgan pozitsiyasini qaytrishdan iborat. Shuning uchun ham bu qidiruv usuli odatda ketma-ket qidiruv deb ataladi. Bu usulda qidiruv algoritmining ish samaradorligi juda past. Bu algoritmni namunaviy misol yordamida o’rganib chiqamiz. Misol. Tasodifiy sonlar bilan to’ldirilgan massivdan oldindan berilgan kalit-qiymatli elementning joylashgan pozitsiyasi (indeksi)ni aniqlang. Yechimi: Buning uchun butun sonli arr[] massivini tavsiflab, uni tasodifiy sonlar generatori rand() funktsiyasi yordamida qiymatlarga to’ldiramiz (misol uchun 50 ta butun son bilan). Klaviaturadan kiritilgan kalit-qiymatga teng bo’lgan qiymatga teng element massivda bor yoki yo’qligini aniqlash funktsiyasi linSearch() ni tavsiflaymiz.
for (int i = 0; i < arrSize; i++) { if (arr[i] == requiredKey) return i; } return -1;
Massivni ekranga chiqaish funksiyasi showArr(): void showArr(int arr[], int arrSize) { for (int i = 0; i < arrSize; i++) { cout << setw(4) << arr[i]; if ((i + 1) % 10 == 0) { cout << endl; } } cout << endl << endl; } Chiziqli qidiruv usuli qo’llanilan dastur. #include #include #include #include #include using namespace std; //funksiy prototipi int linSearch(int arr[], int requiredKey, int size); // chiziqli qidiruv - k-ket qidiruv void showArr(int arr[], int size); // massivni ekranga chiqarish funksiyasi int main() { const int arrSize = 30; int arr[arrSize]; int requiredKey = 0; // qidirilayotgan qiymat (kalit) int nElement = 0; // massiv elementining nomeri srand(time(NULL)); //massivga 1 dan 50 gacha bo'lgan tasodifiy sonlarni yozish for (int i = 0; i < arrSize; i++) { arr[i] = 1 + rand() % 50; } showArr(arr, arrSize); cout << "Qidirilayotgan qiymatni kirit: "; cin >> requiredKey; // ââîä èñêîìîãî ÷èñëà //elementni qidirish va uning positsiyasini eslab qolish nElement = linSearch(arr, requiredKey, arrSize); if (nElement != -1) { //agar element topilsa uning pozitsiyasini ekranga chiqarish cout << "Qidirilayotgan qiymat " << requiredKey << " massivning " << nElement << " -indeksida joylashgan"< }
else {
//agar element topilmasa cout << "Massivda bunday qiymatli son mavjud emas..." << endl;
} return 0;
}
//massivni ekranga chiqarish funksiyasi { for (int i = 0; i < arrSize; i++) { cout << setw(4) << arr[i]; if ((i + 1) % 10 == 0) { cout << endl; } } cout << endl << endl; } //chiziqli qidiruv funksiyasi int linSearch(int arr[], int requiredKey, int arrSize) { for (int i = 0; i < arrSize; i++) { if (arr[i] == requiredKey) return i; } return -1; }
Agar massivdan element topilmasa: 
Agar dastur ishlashiga etibor bersak ushbu algoritm massivda bir xil qiymatli takrorlanuvchi elementlarning faqat birinchisining indeksini qaytaradi. Takrorlanuvchi elementlarning barchasini aniqlash va ekranga chiqarish funksiyasini mustaqil o’rganing va ishlatib ko’ring. Bu algoritmdan elementlarining joylashishi noaniq yoki tartibsiz bo’lgan massivlarga qo’llash aniq samara beradi. Agar massiv elementlari saralanganligi aniq bo’lsa, u holda bunday massivlardan qidiruv uchun binar qidiruv usulini qo’llash tavsiya etiladi. 2. Binar qidiruv usuli Biz chiziqli qidiruv algoritmlarini qarab chiqdik. Qidiruvning boshqa algoritmlari ham mavjud. Masalan, ikkilik (binar) qidiruv algoritmi. Biz yuqorida chiziqli qidiruv algorimtlaridan indeksli ketma-ket qidirish usulini qarab chiqdik. Bunda qayta ishlanayotgan tuzilma elementlarini saralangan bo’lishi kerak edi. Xuddi shunday binar qidiruv algoritmi ham saralangan tuzilmalar ustida qo’llanilsa, yuqori samara beradi. Faraz qilaylik, bizga 12 ta elementdan iborat, o’sish tartibida saralangan quyidagi massiv berilgan bo’lsin: 
Foydalanuvchi tomomnidan kiritilgan qidiruv kaliti asosida qidirilayotgan elementni topish masalasi qo’yilgan. Masalan, kalit 4 ga teng. Birinchi qadamda massiv teng ikkiga bo’linadi (buning uchun o’rta element - midd ni topib olamiz): (0 + 11) / 2 = 5 (bo’linmaning butun qism olinadi, 0.5 tashlab yuboriladi). Birinchi massiv elementlarining o’rta qiymatini tekshiramiz, agar u kalit bilan mos kelsa, algoritm o’z ishini yakunlaydi va topilgan element haqida axborot beradi. Qaralayotgan misolda o’rta qiymat qidirilayotgan kalitga mos kelmaydi. 
Agar qidirilayotgan kalit qiymatli element o’rta qiymatdan kichik bo’lsa, algoritm o’rta qiymatdan katta elementlar joylashgan qismini tekshirmaydi. Qidiruvning o’ng tomondagi chegarasi (midd - 1) ga joylashadi. Hosil bo’lgan qism massivni yana 2 ga bo’lamiz. Qidiruv kaliti yana o’rta elementga teng emas, katta. Endi qidiruvning chap chegarasi (midd + 1) ga joylashadi. 
Uchinchi qadamda o’rta element 3 indeksli elementga teng: (3 + 4) / 2 = 3. U kalitga teng. Algoritm o’z ishini yakunlaydi. Misol: #include using namespace std; // binar qidiruv algoritmi funktsiyasi int Search_Binary (int arr[], int left, int right, int key) { int midd = 0; while (1) { midd = (left + right) / 2; if (key < arr[midd]) // agar qidirilayotgan element kichik bo’lsa right = midd - 1; // qidiruvning o’ng chegarasini aniqlash else if (key > arr[midd]) // agar qidirilayotgan element katta bo’lsa left = midd + 1; // qidiruvning chap chegarasini aniqlash else // yoki (qiymat teng) return midd; // funktsiya ushbu yacheyka qiymatini qaytaradi if (left > right) // agar chegara mos kelmasa return -1; } } int main() { int SIZE; cout << "\n\nMassiv uzunligini kiriting: "; cin>>SIZE; // const int SIZE = 12; int array[SIZE] = {}; int key = 0; int index = 0; // qidirilayotgan qiymatning yacheyka indeksi for (int i = 0; i < SIZE; i++) // massivni to’ldirish va ko’rsatish { array[i] = i + 1; cout << array[i] << " | "; } cout << "\n\nIxtiyoriy sonni kiriting: "; cin >> key; index = Search_Binary (array, 0, SIZE, key); if (index >= 0) cout << "Ko’rsatilgan son quyidagi indeksli yacheykada joylashgan: " << index << "\n\n"; else cout << "Massivda bunday son mavjud emas!\n\n"; return 0; }
Ikkilik qidiruv ketma-ket (chiziqli) qidiriuv algoritmlaridan samarali hisoblanadi, ya’ni uning qiyinlik bahosi O(log2 Misol uchun massiv elementlari 1024 ta bo’lsa, eng yomon holat (qidirilayotgan element massivda yo’q bo’lsa) 1024 ta element ham massivda qidirib ko’rilishi kerak, lekin binar qidirish algoritmida log2(1024)=10 elementni ko’rib chiqish yetarli bo’ladi. Bu birinchi qadamdan keyin 512 ta, ikkinchi qadamdan keyin 256 ta va h.k. elementlar har bir qadamda teng yarmiga qisqarib boraveradi, natijada 10-qadamdan keyin element mavjud emasligi haqidi axborotni chiqaradi. Bu algoritmning kamligi massiv oldindan saralangan bo’lishi talab etilishidir.
3. Download 372.57 Kb. Do'stlaringiz bilan baham: 
|
) ga teng (eslatma, ketma-ket qidiruvda O