Hosted with nbsanity. See source notebook on GitHub.

Binary 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

  1. Define the smallest and largest possible answers (lo, hi).
  2. Write a feasible(x) check that is monotonic: once it becomes true, it stays true for every larger x.
  3. Binary-search for the first x where feasible(x) is true.

Total cost: O(log(range) Ă— cost of feasible).

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 lo

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))  # 30

Example 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))  # 15

How 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.