Taqsimlangan tizimlarda qidiruv algoritmlar

Ikkilik qidiruv algoritmi

Ushbu maqolada biz ikkilik qidiruv algoritmini muhokama qilamiz. Qidiruv - bu ro'yxatdagi ma'lum bir elementni topish jarayoni. Agar element ro'yxatda mavjud bo'lsa, u holda jarayon muvaffaqiyatli deb ataladi va jarayon ushbu elementning joylashuvini qaytaradi. Aks holda, qidiruv muvaffaqiyatsiz deb ataladi.
Chiziqli qidiruv va Ikkilik qidiruv ikkita mashhur qidiruv usullaridir. Bu erda biz Binar qidiruv algoritmini muhokama qilamiz.
Ikkilik qidiruv - saralangan ro'yxatlarda samarali ishlaydigan qidiruv usuli. Shunday qilib, ikkilik qidiruv texnikasidan foydalangan holda biron bir ro'yxatdagi elementni qidirish uchun biz ro'yxatning tartiblanganligiga ishonch hosil qilishimiz kerak.
Ikkilik qidiruv "bo'l va zabt et" yondashuviga amal qiladi, bunda ro'yxat ikkiga bo'linadi va element ro'yxatning o'rta elementi bilan taqqoslanadi. Agar moslik topilsa, o'rta elementning joylashuvi qaytariladi. Aks holda, o'yin davomida olingan natijaga qarab, ikkala bo'limni qidiramiz.

Izoh: Ikkilik qidiruv tartiblangan massiv elementlarida amalga oshirilishi mumkin. Agar ro'yxat elementlari tartiblangan bo'lmasa, avval ularni saralashimiz kerak.

Keling, Binary Search algoritmini ko'rib chiqaylik.

Algoritm

1. 
   Binary_Search(a, pastki_chegara, yuqori_chegara, val) // 'a' - berilgan massiv, 'pastki_chegara' - birinchi massiv elementi indeksi, 'yuqori_chegara' - oxirgi massiv elementi indeksi, 'val' - qiymat qidirish uchun
   
2. 
   1-qadam: beg = pastki_chegara , end = yuqori_chegara , pozitsiya = - 1 ni o'rnating
   
3. 
   2-qadam: beg < =end paytida 3 va 4-bosqichlarni takrorlang
   
4. 
   3-qadam: o'rta = (beg + end)/2 ni o'rnating
   
5. 
   4-qadam: agar a[mid] = val
   
6. 
   pos = o'rtaga qo'ying
   
7. 
   chop etish pos
   
8. 
   6-bosqichga o'ting
   
9. 
   else if a[mid] > val
   
10. 
    o'rnatish end = mid - 1
    
11. 
    boshqa
    
12. 
    beg = o'rta + 1 ni o'rnating
    
13. 
    [end]
    
14. 
    [sikl oxiri]
    
15. 
    5-qadam: agar pos = -1 bo'lsa
    
16. 
    "qiymat massivda mavjud emas" deb chop eting
    
17. 
    [end]
    
18. 
    6-qadam: chiqish