4. Ikkilik qidiruv

Fikr

Saralangan massivda o‘rtadagi elementga qaraymiz. Agar u izlanayotgan
sondan katta bo‘lsa, javob chap yarmida; kichik bo‘lsa — **o‘ng
yarmida**. Har qadamda qidiruv sohasi ikki barobar kichrayadi.

10⁹ ta element ichidan topish uchun atigi ~30 qadam kerak.

Yozuvi

def topish(a, x):
    chap, ong = 0, len(a) - 1
    while chap <= ong:
        orta = (chap + ong) // 2
        if a[orta] == x:
            return orta
        if a[orta] < x:
            chap = orta + 1
        else:
            ong = orta - 1
    return -1

Shart saralanganlik. Saralanmagan massivda ikkilik qidiruv
noto‘g‘ri javob beradi — bu eng ko‘p uchraydigan xato.

Tayyor vosita

import bisect
i = bisect.bisect_left(a, x)    # x ni qo‘yish mumkin bo‘lgan eng chap joy
j = bisect.bisect_right(a, x)   # eng o‘ng joy
soni = j - i                    # x nechta marta uchraydi

Javob bo‘yicha ikkilik qidiruv

Ba’zan massiv yo‘q, lekin javobning o‘zini qidirish mumkin. Buning
uchun «X javob bo‘la oladimi?» degan savolga «ha» yoki «yo‘q» deb javob
beradigan funksiya yoziladi — quyida u boladimi(x). Bu tayyor funksiya
emas: har bir masalada uni o‘zingiz, shu masala shartiga qarab yozasiz.

Usul ishlashi uchun tekshiruv monoton bo‘lishi shart: agar X uchun
«ha» bo‘lsa, X dan katta har qanday son uchun ham «ha». Ya’ni sonlar
bo‘ylab javoblar shunday joylashadi:

x:         1    2    3    4    5    6   ...
boladimi:  yo‘q yo‘q yo‘q ha   ha   ha  ...

Biz birinchi «ha» ni — eng kichik yetarli qiymatni — qidiramiz.

Misol. n berilgan (1 ≤ n ≤ 10¹⁸). x² ≥ n bo‘ladigan eng kichik
natural x ni toping. Bu yerda tekshiruv — x * x >= n: 4 uchun
bajarilsa, 5, 6, … uchun ham albatta bajariladi, ya’ni monoton.

n = int(input())


def boladimi(x):
    # x javob bo‘la oladimi: x² n dan kichik emasmi?
    return x * x >= n


chap, ong = 1, 10**9      # javob shu oraliqda: 10⁹ · 10⁹ = 10¹⁸ ≥ n
while chap < ong:
    orta = (chap + ong) // 2
    if boladimi(orta):
        ong = orta        # orta ham javob bo‘lishi mumkin — uni tashlamaymiz
    else:
        chap = orta + 1   # orta javob emas — undan kattalariga o‘tamiz
print(chap)

n = 10 bo‘lsa: 3² = 9 < 10, 4² = 16 ≥ 10 — javob 4. Taxminan 30
qadamda topiladi, holbuki 1 dan boshlab sanab chiqish 10⁹ qadamgacha
cho‘zilishi mumkin.

Ikkita qoida:

• ong — tekshiruv albatta «ha» bo‘ladigan qiymat bo‘lsin, aks holda

javob oraliqdan tashqarida qolib ketadi;

• tekshiruv teskari bo‘lsa («X uchun «ha» bo‘lsa, kichiklari uchun ham»),

eng katta mos qiymat qidiriladi va shartlar almashtiriladi.

Bu usul bilan «eng kam vaqt», «eng kichik sig‘im», «eng katta
masofa» turidagi masalalar yechiladi.

Cheksiz sikldan ehtiyot bo‘ling

chap < ong va orta = (chap + ong) // 2 bilan chap = orta yozsangiz,
sikl qotib qoladi. Chegaralarni har doim kamida bir birlikka
siljiting.