Binary Search on the Answer: How to Spot the Pattern

The hardest part of "binary search on the answer" is not the code. The code is ten lines and nearly identical every time. The hard part is looking at a problem about shipping packages, eating bananas or splitting an array — with no sorted input anywhere — and realising that a binary search is the intended solution.

This article is about that moment of recognition: what the problem statement is quietly telling you, and why the search is correct when it looks like it has nothing to search.

The problem it solves

A classic shape: packages with weights [3, 2, 2, 4, 1, 4] must ship in order, within 3 days. What is the smallest ship capacity that makes it?

Nothing here is sorted, and the answer is not an element of the input. Trying to construct the optimal split directly leads into a thicket of cases. But notice what is easy: given a specific capacity, checking whether it works takes one greedy pass. Fill each day until the next package would spill over, then start a new day, and count the days.

So the problem splits into two very different questions. "What is the best capacity?" is hard. "Does capacity 7 work?" is trivial. Binary search on the answer turns the hard question into about twenty of the trivial ones.

The intuition

The candidate answers form a range: at least the heaviest single package (otherwise it never fits), at most the total weight (everything in one day). Line up every capacity in that range and ask each one "do you work?"

• Capacity 4: no. Capacity 5: no. Capacity 6: yes. Capacity 7: yes. And so on, yes forever.

The answers form a wall — a run of no followed by a run of yes, never mixed. That shape is the whole requirement. A sorted array is just one way to get it; a monotonic yes/no question over a range of numbers is another. Binary search finds where the wall is, and it does not care which of the two it was given.

If a value works, every larger value works too. That one sentence is what licenses throwing away half the range after each check.

That gives you the three signals to look for in a problem statement:

1. It asks for a minimum or maximum — "smallest capacity", "minimum speed", "largest possible minimum distance".
2. Checking a candidate is much easier than finding the best one. You can write works(x) in a single pass, usually greedily.
3. The check is monotonic. More capacity never hurts; more speed never makes you later. If you can say "if x works, x + 1 works" out loud and believe it, you have the pattern.

The phrases "minimise the maximum" and "maximise the minimum" are almost a direct translation of signal 1 plus signal 3, and they show up in split-array, aggressive-cows and painter-partition problems.

Watch it run

The candidates 4 through 15 are laid out like an array, but no weights are being searched — each probe asks the schedule whether that capacity fits. Watch a no discard everything to its left and a yes discard everything to its right, until one value is left standing.

The code

Write the search once, as "find the first value where the check turns true", and pass the check in. Everything problem-specific lives in the check.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True. ok must be monotonic."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid              # mid works; maybe something smaller does too
        else:
            lo = mid + 1          # mid fails, so everything below it fails
    return lo

def min_capacity(weights, days):
    def fits(cap):                # greedy: fill each day until the next item spills
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used, load = used + 1, 0
            load += w
        return used <= days
    return first_true(max(weights), sum(weights), fits)

def min_speed(piles, hours):
    def finishes(k):              # ceil(p / k) hours per pile
        return sum((p + k - 1) // k for p in piles) <= hours
    return first_true(1, max(piles), finishes)

print(min_capacity([3, 2, 2, 4, 1, 4], 3))   # 6
print(min_speed([3, 6, 7, 11], 8))           # 4

calls = 0
def counted(x):
    global calls
    calls += 1
    return x >= 700_001
print(first_true(1, 1_000_000, counted), calls)   # 700001 20

Two different problems, one search. The last line is the reason the pattern is worth knowing: a million candidates, twenty checks.

A greedy check is exactly the kind of thing that is easy to get subtly wrong, so it is worth testing against something that cannot be wrong. The brute force below tries every way of cutting the list into at most days consecutive runs:

from itertools import combinations
import random

def brute_capacity(weights, days):
    n, best = len(weights), sum(weights)
    for k in range(min(days, n)):
        for cuts in combinations(range(1, n), k):
            edges = (0,) + cuts + (n,)
            best = min(best, max(sum(weights[a:b]) for a, b in zip(edges, edges[1:])))
    return best

random.seed(1)
ok = all(
    min_capacity(ws, d) == brute_capacity(ws, d)
    for ws, d in (
        (w, random.randint(1, len(w)))
        for w in ([random.randint(1, 20) for _ in range(random.randint(1, 9))]
                  for _ in range(3000))
    )
)
print(ok)                                    # True

Three thousand random cases, all agreeing.

The complexity

Each probe costs one run of the check, and the number of probes is the logarithm of the range's width, not of the input's size. For the shipping problem that is O(n · log(sum − max)): a linear check, repeated a logarithmic number of times.

The range width matters less than it looks. Even a range of a billion is about thirty probes. What matters is keeping the check linear — if the check itself is quadratic, the logarithm will not rescue you.

Where it goes wrong

• A check that is not monotonic. Change used <= days to used == days and the wall breaks: capacities 6 to 8 say yes, 9 and above say no again, because a bigger ship finishes early. On the example above the search then returns 16 instead of 6. Phrase the check so that more of the resource can only help.
• Bounds that exclude the answer. Start at 0 instead of the heaviest package and the greedy check miscounts: for a single package of weight 5 and two days, it happily reports that capacity 0 works. Pick bounds you can justify in one sentence each.
• Mixing up the two templates. "Smallest x that works" moves hi = mid. "Largest x that works" — maximise the minimum — flips the wall, and needs mid = (lo + hi + 1) // 2 to avoid an infinite loop when lo and hi are adjacent.
• Real-valued answers. When the answer is a real number, stop on a precision or after a fixed number of iterations rather than on lo < hi.

For the index-based cousins of this template — first occurrence, last occurrence, insertion point — see binary search variants.

How to say it in an interview

"Finding the best capacity directly is hard, but checking one capacity is a greedy linear pass. And the check is monotonic: if capacity c works, anything bigger works too. So I can binary search the capacity between the heaviest package and the total weight, using the check in place of a comparison. That's O(n log(range))."

Then name the monotonicity out loud before writing anything. It is the correctness argument, and saying it first is what separates recognising the pattern from having memorised one problem.