Binary search on the answer always has the same skeleton: you have a yes/no check ok(x) that is monotone (false, false, ..., false, true, true, ...) and you want the first x where it turns true. Write that skeleton once, as a reusable helper.
Write first_true(lo: int, hi: int, ok) -> int:
okis a function taking an int and returning a bool.- Over
lo..hi(inclusive),okis false up to some point and true from then on. ok(hi)is guaranteed to beTrue, so there is always an answer.- Return the smallest
xin[lo, hi]withok(x)true.
first_true(0, 100, lambda x: x * x >= 50) # 8 (7*7 = 49 is not enough)
first_true(1, 10, lambda x: True) # 1 (true everywhere: the answer is lo)
first_true(5, 5, lambda x: True) # 5
Constraints: lo <= hi, and the range can be as wide as 10^18. The tests count your calls to ok: you get about log2(hi - lo + 1) + 2 of them, so scanning upward is out.
Show hint
keep the invariant "the answer is in [lo, hi]": if ok(mid) is true then hi = mid, otherwise lo = mid + 1, and stop when lo == hi.