Bo’lib tashla va xukmronlik qil

Algoritm qadamlari
Ikkilik qidirish algoritmi to'g'ri ishlashi uchun massiv saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular massiv indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi

1. 
   Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli massiv)
   
2. 
   O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
   
3. 
   O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi
   
4. 
   Agar son mos kelsa, algoritm shu joyida to'xtaydi.
   
5. 
   Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1;
   
6. 
   Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1;
   
7. 
   2-qadamga qaytiladi.
   

Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko'p joyda qo'llash mumkin.