What is Binary Search on the Answer?
Learn the binary search on the answer technique, when its feasibility check must be monotonic, and how to explain it in interviews.
Expected Interview Answer
Binary search on the answer is a technique where, instead of searching for a value inside a sorted array, you binary search over the range of possible ANSWERS to a problem, using a feasibility check (a monotonic predicate) at each midpoint to decide whether to search higher or lower.
The key requirement is monotonicity: as the candidate answer increases, a `can(x)` predicate must flip from false to true (or true to false) exactly once, with no oscillation. You pick `lo` and `hi` bounds for the answer space, compute `mid`, run the feasibility check in whatever time it takes (often O(n) or O(n log n)), and shrink the range based on the result. This turns an O(n^2) or worse brute-force search over candidate answers into O(log(range) times cost-of-check). Classic uses include "minimize the maximum load", "find the smallest capacity that ships packages within D days", and "find the k-th smallest element in a matrix" — none of these search a literal array, they search a numeric answer space.
- Turns brute-force answer scanning into logarithmic search
- Works whenever feasibility is monotonic in the answer
- Decouples search cost from feasibility-check cost
- Common pattern for minimize-the-maximum and maximize-the-minimum problems
AI Mentor Explanation
A groundskeeper wants the smallest boundary rope length that still lets every fielder cover their zone without gaps, so instead of testing every possible rope length one by one, they test a middle length and ask a yes/no feasibility question: "does this length cover the ground?" If yes, they try a shorter rope next; if no, they try a longer one. Because feasibility flips cleanly from "no" to "yes" as rope length grows, the groundskeeper halves the search range each time instead of trying every length. This is exactly binary search on the answer — the rope length is the answer being searched, not a value inside a sorted list of ropes.
Step-by-Step Explanation
Step 1
Define the answer range
Pick lo and hi bounding every plausible answer value (e.g. min and max possible capacity).
Step 2
Write a monotonic feasibility check
can(mid) must be false-then-true (or true-then-false) with no oscillation as mid changes.
Step 3
Binary search the range
Compute mid, call can(mid), and shrink lo or hi based on the boolean result, exactly like array binary search.
Step 4
Converge on the boundary answer
When lo == hi, that value is the optimal feasible answer — the exact flip point of the predicate.
What Interviewer Expects
- Recognize the answer space, not an array, is what is being searched
- Prove or state the monotonicity requirement explicitly
- Correctly write the feasibility check and its complexity
- State overall complexity as O(log(range) * cost of check)
Common Mistakes
- Applying binary search on the answer when the predicate is not actually monotonic
- Off-by-one errors in the lo/hi update rules (e.g. mid vs mid+1/mid-1)
- Forgetting to bound the initial answer range tightly, hurting performance
- Confusing this technique with searching a value inside an already-sorted array
Best Answer (HR Friendly)
“Binary search on the answer means I search over possible answers to a problem — like a minimum capacity or a maximum load — the same way I would search a sorted array, using a yes/no check at the midpoint to decide which half to keep. It works whenever that yes/no check flips exactly once as the answer grows, which turns an expensive brute-force search into a fast logarithmic one.”
Code Example
def ship_within_days(weights, days):
def can_ship(capacity):
trips, current = 1, 0
for w in weights:
if current + w > capacity:
trips += 1
current = 0
current += w
return trips <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if can_ship(mid):
hi = mid
else:
lo = mid + 1
return lo # smallest feasible capacityFollow-up Questions
- How do you prove a feasibility predicate is monotonic before applying this technique?
- How would you adapt this to search for the k-th smallest element in a sorted matrix?
- What happens to complexity if the feasibility check itself is O(n log n)?
- How does this differ from standard binary search over a sorted array?
MCQ Practice
1. What property must the feasibility predicate have for binary search on the answer to work?
The predicate must flip from false to true (or vice versa) exactly once as the candidate answer changes, with no oscillation.
2. In the "ship packages within D days" problem, what is the search range?
The technique searches over possible capacity values, bounded below by the heaviest package and above by shipping everything in one trip.
3. What is the overall time complexity of binary search on the answer?
Each of the O(log(range)) iterations runs one feasibility check, so total cost multiplies the two.
Flash Cards
What does binary search on the answer search over? — The space of possible answer values, not an array of data.
What must a feasibility predicate satisfy to use this technique? — Monotonicity — it flips exactly once as the candidate answer increases.
Name a classic use case. — Minimize the maximum load, e.g. "ship packages within D days" or "split array to minimize largest sum".
What is the total time complexity? — O(log(range) times the cost of one feasibility check).