Ikkilik qidiruv

Ikkilik qidiruv saralangan ro‘yxatda qidiruv oralig‘ini har qadamda ikki baravar qisqartiradi: log₂(10⁹) ≈ 30 qadam.

from bisect import bisect_left, bisect_right
k = bisect_right(a, x)     # x dan katta bo‘lmaganlar soni

lo, hi = 0, 10**9          # javob bo‘yicha qidiruv
while lo < hi:
    mid = (lo + hi) // 2
    if ok(mid): hi = mid
    else: lo = mid + 1

Javob bo‘yicha qidiruv

Agar «X yetarlimi?» savoli monoton bo‘lsa (X ishlasa, kattaroq ham ishlaydi), eng kichik X ni ikkilik qidiruv bilan toping. Chegaralar va mid ni yaxlitlashga ehtiyot bo‘ling — cheksiz sikl shu yerdan chiqadi.