def first_true(lo, hi, feasible):
"""Smallest x in [lo, hi] with feasible(x) True; assumes feasible(hi) is True."""
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return loBinary Search on the Answer: A Coding Interview Pattern
Many interview problems don’t look like binary search at all: “What is the minimum ship capacity to deliver all packages in D days?” or “What is the slowest eating speed that still finishes in H hours?” The trick is to binary-search over the answer space instead of over the input array.
The template
- Define the smallest and largest possible answers (
lo,hi). - Write a
feasible(x)check that is monotonic: once it becomes true, it stays true for every largerx. - Binary-search for the first
xwherefeasible(x)is true.
Total cost: O(log(range) Ă— cost of feasible).
Example 1: Koko eating bananas (LeetCode 875)
Piles of bananas, h hours. At speed k, a pile of size p takes ceil(p / k) hours. Find the minimum k. Range: 1 to max(piles).
def min_eating_speed(piles, h):
def feasible(k):
return sum((p + k - 1) // k for p in piles) <= h
return first_true(1, max(piles), feasible)
print(min_eating_speed([3, 6, 7, 11], 8)) # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5)) # 30Example 2: Ship packages within D days (LeetCode 1011)
The capacity must be at least the heaviest package and at most the total weight. The feasibility check greedily fills each day.
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 first_true(max(weights), sum(weights), feasible)
print(ship_within_days([1,2,3,4,5,6,7,8,9,10], 5)) # 15How to spot it in an interview
- The question asks for a minimum maximum or maximum minimum (“smallest capacity”, “largest minimum distance”).
- Checking a given answer is easy, but computing the answer directly is hard.
- The answer is an integer (or can be searched to a precision) within known bounds.
Explain the monotonicity out loud: “If capacity 15 works, any capacity above 15 also works, so I can binary-search.” That sentence is often what the interviewer is waiting for.
Common bugs: wrong lower bound (forgetting max(weights)), integer overflow in other languages (lo + (hi - lo) // 2), and a feasibility function that isn’t actually monotonic.
Disclosure: I work on Linkjob AI, an AI coding interview assistant for live interviews and online assessments.