Tasavvur qiling, telefon daftaridan "Yusupov" familiyasini qidiryapsiz. Siz boshidan boshlab har bir sahifani tekshirmaysiz. Buning o'rniga daftarni o'rtasidan ochasiz — "M" harfiga tushdingiz. "Yusupov" undan keyin, demak chap yarmini tashlab, o'ng yarmi bilan davom etasiz. Har safar qidiruv maydoni ikki barobar kamayadi.
Bu — Binary Search g'oyasi!
Muhim shart: Binary Search faqat tartiblangan listda ishlaydi!
Keling, [1, 3, 5, 7, 9, 11, 13] listdan 9 ni qidirib ko'raylik:
Har qadamda nima sodir bo'ldi:
1-qadam: Listning o'rtasiga qaraymiz — 7. Biz 9 ni qidiryapmiz. 9 > 7, demak 9 o'ng tomonda bo'lishi kerak. Chap yarmini ([1, 3, 5]) butunlay tashlab yuboramiz. Endi faqat [9, 11, 13] qoldi.
2-qadam: Qolgan qismning o'rtasiga qaraymiz — 11. 9 < 11, demak 9 chap tomonda. O'ng yarmini ([13]) tashlaymiz. Endi faqat [9] qoldi.
3-qadam: O'rtaga qaraymiz — 9. Aynan shu! Topildi!
Faqat 3 qadam ketdi. Agar Linear Search bilan qidirganimizda, boshidan har birini tekshirib, 5 qadam kerak bo'lardi. List qancha katta bo'lsa, bu farq shuncha katta bo'ladi.
Keyingi darsda Binary Search ni kodda yozamiz.