Binary Search on an Answer Space

Most people learn binary search as “find a value in a sorted array”. The more useful version in interviews never touches a sorted array at all. You’re asked for the smallest capacity, the slowest speed or the largest gap that satisfies some rule, and the trick is to binary search over the possible answers rather than over the input.

It works whenever you can write a yes-or-no question about a candidate answer, and that question’s answer changes only once as the candidate grows. Everything else in this note is detail on top of that one idea.

Recognising the pattern

The wording usually gives it away. Look for “minimum capacity such that…”, “smallest speed so that…”, “maximise the minimum distance”, or “minimise the largest sum”. Each of those phrases describes an optimum over a range of numbers, with a constraint attached.

Then check the property that makes it work. Call the yes-or-no question feasible(x). For a minimisation problem it must be monotonic: if x works, every value larger than x also works. Lay feasible out over the range and you get a run of False followed by a run of True, and the answer is the first True. Binary search finds that boundary in O(log(range)) calls instead of trying every value.

If you can’t argue monotonicity, stop. Binary searching a predicate that flips back and forth returns an arbitrary boundary, and no amount of careful indexing fixes that.

Worked example: shipping packages within D days

A conveyor belt carries packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], in that order. Each day you load packages onto a ship in order until the next one would exceed the ship’s capacity. What’s the smallest capacity that ships everything within 5 days?

Start with the feasibility check, because it’s the part you can reason about independently. Given a capacity, simulate the loading greedily and count the days:

def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:      # this package starts a new day
            days += 1
            load = 0
        load += w
    return days

The greedy fill is optimal for a fixed capacity: packages must ship in order, so filling today as much as possible can never push a later package onto a later day than some other plan would. That’s the short exchange argument you’d give if asked.

Monotonicity is easy to see: a bigger ship never needs more days. Printing the predicate over capacities 10 to 19 shows the expected shape:

predicate: {10: False, 11: False, 12: False, 13: False, 14: False, 15: True, 16: True, 17: True, 18: True, 19: True}

Now the search. The answer can’t be smaller than the heaviest package (a package can’t be split across days) and never needs to exceed the total weight (one day carries everything). So the range is [max(weights), sum(weights)]:

def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)      # answer is somewhere in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= days:
            hi = mid                         # mid works; maybe something smaller does too
        else:
            lo = mid + 1                     # mid fails, so does everything below it
    return lo

With a trace line added inside the loop, here’s every probe the search made:

lo=10 hi=55 mid=32 days_needed=2 -> feasible
lo=10 hi=32 mid=21 days_needed=3 -> feasible
lo=10 hi=21 mid=15 days_needed=5 -> feasible
lo=10 hi=15 mid=12 days_needed=6 -> too small
lo=13 hi=15 mid=14 days_needed=6 -> too small
answer: 15

Five calls to days_needed instead of up to 46 for a linear scan over capacities. Notice the asymmetry in the updates. When mid is feasible, hi = mid keeps it in range, because it might be the answer. When mid fails, lo = mid + 1 throws it out, because a failing capacity can’t be the answer. The loop ends when lo == hi, and that single remaining value is the first feasible capacity. Two other inputs give 6 for [3, 2, 2, 4, 1, 4] in 3 days and 3 for [1, 2, 3, 1, 1] in 4 days.

Time is O(n log S), where n is the number of packages and S the total weight: each of the log S probes runs one O(n) simulation. Extra space is O(1).

Bounds that are too loose can break the check

It’s tempting to start with lo = 1 and let the search sort it out. Sometimes that’s harmless; here it isn’t. The feasibility function assumes no single package exceeds the capacity. Give it a capacity smaller than the heaviest package and it happily “loads” the oversized package anyway:

lo=1 version: 2  correct: 10

That’s [10, 1, 1] in 3 days. With capacity 2, days_needed opens a new day for the 10, overloads it, and still counts only 3 days, so the search reports 2. The predicate isn’t wrong for valid inputs; it’s undefined for capacities that can’t work, and a loose bound feeds it exactly those. Either make the lower bound tight (max(weights)) or make the check return False when w > capacity. Doing both is fine.

The upper bound matters less for correctness, but it should be a value you can prove is feasible. If hi itself might be infeasible and the search never finds a true value, lo ends at hi and you’d return an answer that doesn’t work.

The mirrored version: maximise the minimum

Some problems ask for the largest value that still works. Placing 3 balls into baskets at positions [1, 2, 3, 4, 7] so that the smallest distance between any two balls is as large as possible is the classic example. Now the predicate is monotonic the other way: if you can keep every pair at least gap apart, you can certainly keep them gap - 1 apart. So you have a run of True followed by False, and you want the last True.

def can_place(positions, balls, gap):
    count, last = 1, positions[0]
    for p in positions[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count >= balls

def max_min_distance(positions, balls):
    positions = sorted(positions)
    lo, hi = 1, positions[-1] - positions[0]
    while lo < hi:
        mid = (lo + hi + 1) // 2          # round up, or lo = mid can loop forever
        if can_place(positions, balls, mid):
            lo = mid                      # mid works; try a bigger gap
        else:
            hi = mid - 1
    return lo

This returns 3 for the example (balls at 1, 4 and 7) and 999999999 for [5, 4, 3, 2, 1, 1000000000] with 2 balls. The rounding is the bit people get wrong. When lo = 4 and hi = 5, rounding down gives mid = 4; if that’s feasible, lo = mid leaves lo at 4 and the loop never ends. Rounding up gives mid = 5, which always makes progress. The rule of thumb: whichever side keeps mid (lo = mid or hi = mid), round mid away from that side.

Interview practice: Koko eating bananas

Koko has piles of bananas, for example [3, 6, 7, 11], and h = 8 hours. Each hour she picks one pile and eats up to k bananas from it; if the pile has fewer than k, she finishes it and waits out the hour. What’s the minimum integer speed k that lets her finish within h hours? Explain the search range and the check, then give the complexity.

Answer

The predicate is “at speed k, does she finish within h hours?”. A pile of size p takes ceil(p / k) hours, so the total is the sum of those over all piles. Eating faster never takes longer, so the predicate goes False ... False True ... True as k grows, and we want the first True.

The range is [1, max(piles)]. Speed 1 is the slowest meaningful value, and speed max(piles) finishes every pile in one hour each, which is feasible whenever h is at least the number of piles (the problem guarantees it). Going higher than the largest pile never helps, since she can’t eat from two piles in one hour.

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        k = (lo + hi) // 2
        hours = sum((p + k - 1) // k for p in piles)   # ceil(p / k) without floats
        if hours <= h:
            hi = k
        else:
            lo = k + 1
    return lo

[3, 6, 7, 11] 8 -> 4
[30, 11, 23, 4, 20] 5 -> 30
[30, 11, 23, 4, 20] 6 -> 23
[1000000000] 2 -> 500000000

Time is O(n log M), with M the largest pile; space is O(1). Two things an interviewer may follow up on: the integer ceiling (p + k - 1) // k avoids floating-point surprises with large piles, and in Java or JavaScript the hour total can exceed 32-bit range for big inputs, so use a long (or check hours > h and stop early). You can run your own version against the tests on Koko Eating Bananas.

More to read

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Binary Search and Explicit Boundaries, on interval conventions and loop invariants
• Big-O Complexity and Input Growth, for why log S probes are cheap
• MIT 6.006 Introduction to Algorithms (Spring 2020)