Cavab üzərində ikili axtarış

İkili axtarışı massivin elementləri üzərində yox, mümkün cavablar üzərində tətbiq etmək olar. Şərt: cavabı yoxlayan ok(x) funksiyası monotondur: False ... False True ... True. Onda ən kiçik True-nu O(log(aralıq)) yoxlama ilə tapırıq. Sərhəd şablonları üçün: ikili axtarışın tələləri.

Şablon

[lo, hi] aralığında ən azı bir True olmalıdır (adətən hi təminat verir). Dövr: mid-i hesabla; ok(mid) doğrudursa mid cavab ola bilər, deməli hi = mid; əks halda cavab mid-dən böyükdür, lo = mid + 1. lo == hi olanda cavab tapılıb. Bu, yarıaçıq şablonun ("birinci True") eynisidir.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True; ok must be monotone."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid              # mid works: look for a smaller answer
        else:
            lo = mid + 1          # mid fails: the answer is bigger
    return lo

# the smallest x with x * x >= 50
print(first_true(0, 50, lambda x: x * x >= 50))
# the smallest even number above 1000
print(first_true(0, 5000, lambda x: x % 2 == 0 and x > 1000))

8
1010

Monotonluğun əsaslandırılması