Javob bo‘yicha ikkilik qidiruv

Javob bo‘yicha binar qidiruv

G‘oya

Ba’zan biz massivdagi elementni emas, balki shartni qanoatlantiradigan eng kichik yoki eng katta javobni izlaymiz.

Yondashuv shunday:

• mumkin bo‘lgan javob mid ni ko‘rib chiqamiz;
• tekshiramiz: mos keladimi yoki yo‘qmi;
• agar mos kelsa — javobni yaxshiroq qilishga urinib ko‘ramiz;
• agar mos kelmasa — keyinroq izlaymiz.

Asosiy shart

Monotonlik bajarilishi kerak:

• agar mid mos kelsa, unda barcha kattaroq (yoki, boshqa qo‘yilishda, barcha kichikroq) qiymatlar ham mos keladi;
• agar mid mos kelmasa, unda barcha kichikroq (yoki kattaroq) qiymatlar ham mos kelmaydi.

Aynan shu xossa javob bo‘yicha binar qidiruvni qo‘llashga imkon beradi.

Shablon

Masala misoli

Butun son $n$ berilgan, $x \geq n^2$ bo‘lgan minimal butun son $x$ ni topish talab qilinadi.