Binary Search on the Answer
Sometimes you cannot binary search the input, but you can binary search the answer itself. This works when the question is an optimization, like minimizing a maximum, and a yes or no feasibility check is monotonic.
The monotonic test
The key insight is that there is a threshold: every candidate answer below it fails and every candidate at or above it succeeds, or the reverse. Because the feasibility pattern looks like no no no yes yes yes, you can binary search for the boundary:
- Guess a candidate answer in the middle of the range.
- Run a feasibility check that returns whether that candidate is achievable.
- Move the search bounds toward the smallest feasible value.
A worked example
To split an array into k parts minimizing the largest part sum, guess a maximum sum and greedily check if k parts suffice. Larger guesses are always easier, so the check is monotonic and binary search finds the smallest workable maximum.
Key idea
When feasibility flips once from no to yes, binary search the answer space for that threshold.