3-Mavzu: Binar qidiruv. Qidiruv

3-Mavzu: Binar qidiruv.
Qidiruv.

• 
  Qidiruv deb biror berilgan to’plam elementlardan berilgan sonni izlashga aytiladi. Masalan massiv elementlari ichidan sonni qidirish.
  
• 
  Massiv: 45, 12 , 89, 12, -78, 12;
  
• 
  12 sonining pozitsiyalari 2, 4, 6;
  
• 
  Oddiy chiziqli qidiruvda massivning har bir elementi bilan tekshirib chiqamiz.
  
• 
  Har bir so’rovga O(n) amallar bajariladi.
  

Chiziqli qidiruvning kamchiligi agar so’rovlar soni m ta bo’lsa har bir so’rov uchun n ta amal talab qilingani uchun umumiy taqqoslashlar soni n*m bo’ladi. Agar n=m=10⁵ tartibda bo’ladigan bo’lsa, u holda 10¹⁰ amal talab qilinadi. Buni esa EXM qisqa vaqt ichida bajara olmaydi. Shuning uchun binar qidiruvdan foydalanamiz.
Binar qidiruv

• 
  Bizga o’sish tartibda saralangan bir o’lchamli massiv berilgan:
  
• 
  4 6 8 10 15 20 21 50 63
  
• 
  Va biror son beriladi. Maqsad bu son berilgan massivda bor yoki yo’qligini aniqlash. Agar bor bo’lsa uning pozitsiyasini chiqarish. Masalan 10 soni massivda bor va pozitsiyasi 4. 16 soni esa massivda yo’q. Massivda yo’q bo’lsa bunga javob tariqasida masalan -1 ni javob sifatida qaytarish mumkin.
  
• 
  Chiziqli qidiruv orqali har bir so’rov uchun O(n) javob bersak, agar savollar soni m ta bo’lsa O(nm) operatsiya talab qilinadi.
  
• 
  Binar qidiruv algoritmi har bir savolga javobni tez topishga imkon beradi.
  

Bu algoritm qanday ishlashini ko’rib chiqamiz:

• 
  Hamisha bizda uchta son mavjud: bular element izlayotgan massiv indekslari chegarasi: L(left, chap) va R(right, ong) indekslar va izlanayotgan x soni; Dastlab L=1, R = n+1; O’ng index tegishlli emas. Ya’ni dastlab sonni butun massivdan izlaymiz. O’ng (right) chegara massivdan o’ng tomondagi birinchi indeks va u berilgan massivga tegishli emas.
  

• 
  Har safar berilgan kesma o’rtasidagi elementni tanlaymiz va uni izlanayotgan element bilan taqqoslaymiz.
  
• 
  O’rtadagi element indeksi esa quyidagiga teng: m = (L+R) / 2;
  
• 
  Agar o’rtadagi element izlanayotgan sondan katta bo’lsa qidiruvni o’ng tamondan chegaralaymiz. l Chunki massiv kamaymaslik tartibda saralangani uchun o’rtadagi element iznanayotgan sondan katta bo’lganligi sababli undan o’ng tamondagi barcha sonlar izlanayotgan sondan katta bo’ladi va ularning bizga endi keragi bo’lmaydi. Izlanayotgan interval [L, m] ga o’tadi.
  
• 
  Aks holda chap tamondan chegaralayzim. Izlanayotgan interval [m, R] ga o’tadi.
  
• 
  Demak harbir amalda izlanayotgan interval uzunligi 2 marta kamayadi. Har bir amalda 2 marta kamaysa u holda k ta amaldan so’ng 2^k marta kamayadi. Dastlab interval uzunligi n ga teng bo’lganligi uchun uning 1 gacha kamayishi uchun ketadigan amallar sonini esa quyidagich aniqlaymiz.
  

2^k=n => k=log₂(n). Ya’ni umumiy amallar soni log(n) ga teng bo’ladi. Bu asa n ning qiymati 10⁵ atrofida bo’lganda taxminan 17 ga teng bo’ladi. Demak binar qidiruv algoritmida har bir izlash haqidagi so’rovga shuncha amal bajarish orqali javob berish mumkin.
Masalan 22 sonini qidiraylik:
1) O’rtadagi element 17 ga teng, 22≥17 bo’lganligi uchun uni o’ng tamondan izlashni davom ettiramiz.

2) Endi o’rtadagi element 30 ga teng. 22<30 bo’lganligi uchun endi uni chap tomondan izlaymiz.

3) Bu safar o’rtadagi element 22 ga teng 22≥22 bo’lganli uchun endi izlashni o’ng tomondagi intervaldan davom ettiramiz.

4) O’rtadagi element 25, 22<25 bo’lganligi uchun intervalni chap tomondan davom ettiramiz.

Nihoyat izlanayotgan intervalning chegaralari bir yerga kelib qoldi ya’ni R=L+1 bo’ldi. R indeksni dastlab massivga tegishli bo’lmagan indeks qilib oldik. Izlanayotgan massiv indeksi L o’zgaruv bo’ladi. Biz bu indeksni topdik, lekin iznalayotgan son massivda yo’q bo’lishi mumkin. Buni tekshirish uchun esa topilgan indeksdagi massiv elementining izlanayotgan songa tengligini tekshirish yetarli bo’ladi ya’ni ya’ni if (a[L]==x).

•