Binary Search on Answer
Search a numeric answer space whose feasibility changes only once.
The idea
Binary search does not require a stored sorted array. It only needs an ordered candidate space and a monotonic predicate: small candidates fail, then all sufficiently large candidates succeed.
Choose defensible lower and upper bounds, test the midpoint with a feasibility function, and keep narrowing toward the first value that works.
Turn a dial upward until a machine can finish its workload in time. Once a setting works, every stronger setting works too, so binary search finds the first sufficient click.
When to reach for it
- The question asks for a minimum possible maximum or maximum possible minimum.
- You can check one candidate faster than constructing the answer directly.
- Feasibility is monotonic across a bounded numeric range.
Language-independent template
left, right = answer_bounds
best = right
while left <= right:
mid = midpoint(left, right)
if feasible(mid): best, right = mid, mid - 1
else: left = mid + 1
return bestComplexity — time O(n log R), space O(1) (R is the width of the numeric answer range).
Common mistakes
- Searching invalid bounds that cannot contain the answer.
- Reversing the boundary update after a feasible check.
- Using a non-monotonic feasibility predicate.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the largest complete staircase height.
Find the minimum eating speed that finishes within h hours.
Split into m parts while minimizing the largest part sum.