Бинарный поиск по ответу

Бинарный поиск можно применять не к элементам массива, а к множеству возможных ответов. Условие: функция проверки ok(x) монотонна: False ... False True ... True. Тогда наименьшее True находится за O(log(диапазон)) проверок. О границах и шаблонах: ловушки бинарного поиска.

Шаблон

В [lo, hi] должно быть хотя бы одно True (обычно его гарантирует hi). Цикл: считаем mid; если ok(mid) истинно, то mid может быть ответом, значит hi = mid; иначе ответ больше mid, lo = mid + 1. При lo == hi ответ найден. Это тот же шаблон «первый True», что и в lower_bound.

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

Обоснование монотонности