Binary Search on the Answer: Recognising the Pattern in Interviews

Some interview problems look like optimisation puzzles: "minimum capacity to ship packages in D days", "smallest maximum pages per student", "minimum speed to eat all bananas in H hours". There's no sorted array in sight, yet the intended solution is binary search. The trick is that you search over the answer space.

The signal

Ask: if I guess an answer X, can I cheaply check whether X is feasible? And is feasibility monotonic: if X works, does every larger X also work? When both are true, the feasible answers form a contiguous block, and binary search finds its edge in O(log range) checks.

The template

lo, hi = smallest_possible, largest_possible
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid        # mid works; try smaller
    else:
        lo = mid + 1    # mid fails; need bigger
return lo

Using lo < hi with hi = mid avoids the classic infinite loop and lands exactly on the smallest feasible value.

Worked example: shipping capacity

Weights must ship in order within D days. The lower bound is the heaviest single package (anything smaller can never ship it); the upper bound is the total weight (one day). feasible(cap) greedily fills each day until the next package would overflow, counts days, and returns days <= D. That check is O(n), so the whole solution is O(n log(sum)).

How to explain it to the interviewer

1. Say the answer is bounded between L and R and why.
2. Describe the greedy feasibility check and its cost.
3. Argue monotonicity in one sentence: "more capacity never needs more days".
4. Give the total complexity.

The monotonicity sentence is what interviewers listen for; it proves you know why binary search applies, not just that you've seen the problem.

Common slips

• Lower bound of 0 or 1 instead of the true minimum, which makes the check reason about impossible cases.
• Using floating point when the answer is an integer.
• Writing feasible with an off-by-one in the day count: start the counter at 1, not 0.

Disclosure: I help build Linkjob AI, an interview copilot. These notes are general study material.