Guruhi talabasining

Chiziqli qidirish algoritmi 
Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u massivdagi har bir 
elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm 
murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin. 
Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z 
profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan 
foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10
⁶ ta loginni 
tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya 
(16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga 
samaraliroq algoritmlar kerak bo'ladi.
Ikkilik qidirish algoritmining ishlash prinsipi
Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter 
bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha:
1. Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu 
sonni iloji boricha kam taxmin ishlatgan holda topish.
2. Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter 
o'ylagan sondan katta yoki kichikligini aytadi.

---

3. Agar sizning taxminingiz kompyuter o'ylagan son bilan bir xil bo'lsa, o'yin 
tugaydi.
Xo'sh, bunda kamroq yo'l tutish uchun nima qilgan bo'lar edingiz?
Albatta, birinchi navbatda o'rtadagi sonni taxmin qilib ko'ramiz, ya'ni 50 ni(6.4-
rasm):
6.4-rasm. Ikkilik qidirish algoritmining ishlash prinsipi.
Aytaylik kompyuter bizga taxminimiz o'ylangan sondan kichikroq ekanligini 
aytdi. Demak, endi biz 50 va undan kichik barcha son o'ylangan sondan kichik 
ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi 
(50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o'rtasidagi 
sonni olamiz, ya'ni 75 ni(6.5-rasm).
6.5-rasm. Ikkilik qidirish algoritmining ikkinchi qadami.
Kompyuter bizga 75 o'ylangan sondan katta ekanligini aytdi. Demak, 75 dan 
katta barcha sonlar ham o'ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish 
sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz 
o'ylangan sonni topishimiz mumkin(6.6-rasm).
6.6-rasm. Ikkilik qidirish algoritmining keyingi qadamlari.
Sonlar 100 ta bo'lgan holatda, biz har qanday tahminni ko'pi bilan 7 ta qadamda 
topishimiz mumkin bo'ladi. Ikkilik qidirish algoritmi ham huddi shunday prinsipda 
ishlaydi!