Binary Search on the Answer
Intermediate · 18 min read · Problem-Solving Patterns, Searching & Sorting
When the answer is a number and "can I do it with X?" is monotonic.
Some problems look nothing like binary search. "What's the minimum ship capacity to deliver everything in 5 days?" "What's the slowest eating speed that still finishes in time?" There's no sorted array in sight. But there's a hidden one: the range of possible answers.
This is one of the highest-value patterns to learn: it turns many "hard-looking" optimisation problems into a simple check plus ten lines of search.
The recipe
Total cost: O(n · log(range)).
Worked problems
(p + k − 1) / k is the integer ceiling — avoid Math.ceil on doubles, which invites rounding bugs.
Minimise vs maximise
Practice ladder
Interview questions
- How do you know binary search on the answer applies?
- Why is the greedy check correct for ship capacity?
Further reading
Key takeaways
- When the answer is a number and "does x work?" flips once, binary search over the answers.
- Recipe: range → feasibility check (often greedy, O(n)) → confirm monotonic → first true.
- Minimise / minimise-the-max → first true; maximise / maximise-the-min → first false − 1.
- Many "different" problems share one check (ship capacity = split array = painters).
- Use long in checks, integer ceilings, and test impossibility first.