Binary Search on the Answer
Guess the result and check feasibility.
Guess, Then Verify
Sometimes you cannot compute the answer directly, but you can check a guess. Binary search on the answer turns hard optimization into easy checking.
# guess X, ask: is X feasible?The Magic Property
It works when feasibility is monotonic: if a value works, every larger (or smaller) value also works. That ordering is what you search.
# feasible(X) true => feasible(X+1) trueAll lessons in this course
- Classic Binary Search Without Bugs
- bisect_left and bisect_right
- First True: Predicate Binary Search
- Binary Search on the Answer