Binary Search on Answer

Binary search over a monotonic answer space to find the minimum or maximum feasible value rather than searching in the input directly.

Binary search over a monotonic answer space to find the minimum or maximum feasible value rather than searching in the input directly.

The optimal answer always lies within [lo, hi]; lo advances when mid is feasible, hi retreats when it is not.

A monotonic feasibility function divides the answer space into a prefix of infeasible values and a suffix of feasible ones — binary search finds the boundary in O(log(range)) steps.

Each iteration calls the feasibility check once at O(n), giving O(n log(range)) total.