Taqsimlangan tizimlarda qidiruv algoritmlar

Ikkilik qidiruvning ishlashi

Keling, ikkilik qidiruv algoritmining ishlashini ko'rib chiqaylik.
Ikkilik qidiruv algoritmining ishini tushunish uchun tartiblangan massivni olaylik. Ikkilik qidiruvning ishlashini misol bilan tushunish oson bo'ladi.
Ikkilik qidiruv algoritmini amalga oshirishning ikkita usuli mavjud -

• 
  Iterativ usul
  
• 
  Rekursiv usul
  

Ikkilik qidiruvning rekursiv usuli “bo‘l va zabt et” yondashuviga amal qiladi.
Massivning elementlari - bo'lsin.

1.5-rasm. Binary search uchun berilgan massiv
Qidiriladigan element K = 56 bo'lsin
Massivning o'rtasini hisoblash uchun quyidagi formuladan foydalanishimiz kerak -

1. 
   mid = (begin + end)/2
   

Shunday qilib, berilgan massivda -
begin = 0
end = 8
mid = (0 + 8)/2 = 4. Demak, 4 - massivning o'rtasi.

1.6-rasm. Binary search algoritmi birinchi qadamini bajarilishi

1.7-rasm. Binary search algoritmi ikkinchi qadamini bajarilishi



1.6-rasm. Binary search algoritmi uchinchi qadamini bajarilishi

Endi qidirish uchun element topildi. Shunday qilib, algoritm mos keladigan element indeksini qaytaradi.

Ikkilik qidiruvning murakkabligi

Keling, eng yaxshi holatda, o'rtacha va eng yomon holatda Ikkilik qidiruvning vaqt murakkabligini ko'rib chiqaylik. Ikkilik qidiruvning kosmik murakkabligini ham ko'ramiz.

1. Vaqtning murakkabligi

Case	Vaqtning murakkabligi
Eng yaxshi holat	O(1)
Oʻrtacha holat	O (logn)