Binary Search on the Answer: An Interview Pattern for Min-Max Problems
Most people learn binary search as "find a target in a sorted array." In interviews, a more powerful version shows up constantly: you don't search the array at all. You search over the range of possible answers, and for each guess you ask a simple yes/no question: "Is this answer good enough?"
This guide explains the binary search on the answer interview pattern: how to recognize it, how to structure the code, and how to explain why it works.
How to recognize it
Signals that point to this pattern:
- The question asks for the minimum possible maximum or the maximum possible minimum. For example: "minimize the largest sum," "maximize the minimum distance."
- It asks for the smallest speed, capacity, or time that makes something possible.
- Checking whether a specific answer works is easy, but finding the best answer directly is hard.
- The answer is a number in a range you can bound, like
1tosum(nums).
Classic examples:
- Koko eating bananas: minimum eating speed to finish in h hours.
- Capacity to ship packages within d days.
- Split array largest sum.
- Aggressive cows / magnetic force between balls: maximize the minimum gap.
- Minimum days to make m bouquets.
The key property: monotonicity
The pattern works when feasibility is monotonic. If a ship capacity of 15 works, then 16, 17, and every larger capacity also work. If 14 fails, everything smaller fails too. So the answers look like:
fail fail fail fail PASS PASS PASS PASS
Binary search finds the first PASS in O(log range) checks. Saying this out loud is the most important part of your explanation.
The template
def min_feasible(lo, hi, feasible):
# smallest value in [lo, hi] for which feasible(value) is True
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid works; maybe something smaller works too
else:
lo = mid + 1 # mid fails; answer is larger
return lo
For "maximize the minimum," flip it:
def max_feasible(lo, hi, feasible):
while lo < hi:
mid = (lo + hi + 1) // 2 # round up to avoid an infinite loop
if feasible(mid):
lo = mid
else:
hi = mid - 1
return lo
The rounding detail in the second version is a classic source of infinite loops. Mentioning it shows care.
Worked example: ship packages within D days
Given package weights in order and a number of days, find the minimum ship capacity that ships everything in time.
Bounds:
- Lower bound:
max(weights), since the ship must carry the heaviest package. - Upper bound:
sum(weights), which ships everything in one day.
Feasibility check: greedily load packages day by day; start a new day when the next package would exceed capacity.
def ship_within_days(weights, days):
def feasible(cap):
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return used <= days
return min_feasible(max(weights), sum(weights), feasible)
Complexity: the check is O(n), and we run it O(log(sum − max)) times, so O(n log S) overall.
Worked example: maximize the minimum distance
Place k items at given positions to maximize the smallest gap between any two.
def max_min_distance(positions, k):
positions.sort()
def feasible(gap):
count, last = 1, positions[0]
for p in positions[1:]:
if p - last >= gap:
count += 1
last = p
return count >= k
return max_feasible(0, positions[-1] - positions[0], feasible)
Talk track for the interview
- Reframe: "Instead of finding the best capacity directly, I'll guess a capacity and check if it works."
- Monotonicity: "If a capacity works, any larger one also works, so the feasible answers form a contiguous range."
- Bounds: "The answer is at least the max weight and at most the total."
- Check: "For a given guess, a greedy pass tells me how many days I need, in O(n)."
- Complexity: "O(n log S), where S is the size of the search range."
Common bugs
- Wrong bounds. A lower bound of 0 or 1 can make the check behave strangely; think about the smallest answer that could possibly work.
- Infinite loops. With
lo = mid, round mid up. - Off-by-one in the check. Is the condition
<=days or<days? Test with a tiny example. - Non-monotonic checks. If larger answers don't always stay feasible, this pattern doesn't apply. Say you verified it.
- Floating-point answers. For continuous answers, loop a fixed number of times (say 100) instead of
while lo < hi.
How it relates to other patterns
The feasibility check is often greedy, sometimes a BFS, sometimes a prefix sum. Binary search on the answer is the outer loop that wraps one of those. When you see "minimize the maximum," think: "What's the cheapest way to check one guess?"
Practice the reframe out loud
The hardest part of this pattern isn't the code. It's noticing the reframe under pressure and explaining it clearly. Luna Interview helps you practice talking through problems like this with a timer running, so the insight comes out calmly when it counts.
Work through the five classic problems above and say the talk track every time. After a week, "minimize the maximum" will trigger this pattern automatically.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.