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:
Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi.
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(3-rasm):
3-rasm. Ikkilik qidirish algoritmini 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.
4-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.
5-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!
Keyin kichik vazifa uchun samarali algoritmni qo'llaymiz. Shundan so’ng natijalarni asosiy vazifaning mohiyatiga qarab birlashtiramiz. Masalan, matritsani ko’paytirishning cache-oblivious algoritmi har bir matritsani to'rtta kichik matritsaga rekursiv ravishda bo'lish orqali hosil bo’ladi. Matritsa to’liq holda keshga joylashganda kichik masalalarga mo’ljallangan optimallashtirilgan algoritmdan foydalanamiz, keyinchalik funktsiyalar natijasini matritsaga qo'shamiz.
|
