Binary search can be applied not to array elements but to the space of possible answers. The condition: the check function ok(x) is monotone: False ... False True ... True. Then the smallest True is found with O(log(range)) checks. For boundaries and templates: binary search pitfalls.

The predicate is `False` below 15 and `True` from 15; the search finds the answer in 3 checks
The predicate is False below 15 and True from 15; the search finds the answer in 3 checks

The template

The range [lo, hi] must contain at least one True (usually hi guarantees it). The loop: compute mid; if ok(mid) holds, mid may be the answer, so hi = mid; otherwise the answer is above mid, lo = mid + 1. When lo == hi the answer is found. This is the same "first True" template as in lower_bound.

python
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))
text
8
1010

Justifying monotonicity