Laboratoriya ishi

Ikkilik (binar) qidirish algoritmi. Qidirilayotgan elementni saralangan ro’yxatning o’rtasidagi element bilan taqqoslash natijasida quyidagi uchta holatdan biri bo’lishi mumkin: qidirilayotgan element topildi, o’rtadagi elementdan kichik yoki katta. Birinchi (eng yaxshi) holatda qidiruv tugallanadi. Qolgan ikki holatda ro’yxatning yarmini tashlab yuborish mumkin.

Qidirilayotgan qiymat o’rta elementdan kichik bo’lsa, u holda bu qiymat o’rta qiymatdan oldin, aks holda (katta bo’lsa), o’rta qiymatdan keyin joylashgan bo’ladi. Bu prosedura yana takrorlanishi natijasida ajratib olingan qismro’yxatning yana yarmini tashlab yuborish mumkin bo’ladi. Natijada quyidagi algoritmga ega bo’lamiz:

binarySearch (list, target, N)

{list – qaraladigan ro’yxat nomi, target – qidirilayotgan qiymat, N – ro’yxatdashgi elementlar soni }

start=1

end=N

while start<=end do

middle=(start+end)/2

select (Compare(list[middle],target)) from

case -1: start=middle+1

case 0: return middle

case 1: end=middle-1

end select

end while

return 0

Bu algoritmda agar qidirilayotgan qiymat o’rta qiymatdan oshib ketsa, start o’zgaruvchisiga middle qiymatidan bir birlikka ko’p qiymat ta’minlanadi, aks holda (kichik bo’lsa), middle qiymati bir birlikka kamaytiriladi. Natijada tanlab olingan o’rta qiymat qidirilayotgan qiymat emasligi aniqlanib, o’rta qiymatni qayta solishtirishdan chiqarib yuborish mumkin bo’ladi.