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 tomonidan kiritilgan qidiruv kaliti asosida qidirilayotgan elementni topish masalasi qo’yilgan. Masalan, kalit 4 ga teng bo’lsin.
Agar C – taqqoslashlar soni va n – jadvaldagi elementlar soni bo’lsa, u holda
Masalan, n = 1024, bo’lsa,
Ketma-ket qidiruvda C = 512, binar qidiruvda esa C = 10.
Agar katta hajmdagi ma’lumotlar ichida qidiruv amalga oshirilayotgan bo’lsa, u holda binar va indeksli ketma-ket qidiruvni umumlashtirib olib borish mumkin. Sababi, har ikkala qidiruv ham tartiblangan massivda amalga oshiriladi.
Bu algoritmning kamchiligi massiv oldindan saralangan bo’lishi talab etilishidir.
20. Binar qidiruv algoritmining asosiy funktsiyasini S++ dasturlash tilida yozing va uning ishlashini tushuntirib bering?
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; } }
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.
