Binary Search on the Answer

Most binary searches scan a sorted array of data. But some problems have no array to search at all — instead they ask for a single number (a minimum speed, a smallest capacity, a largest gap) where you can check any guess but cannot directly compute the answer. The trick is to binary-search the space of possible answers itself. This is one of the highest-leverage patterns in interviews because once you spot it, a problem that looked like brute force collapses to a tidy O(n log range).

Intuition

Imagine you are buying the slowest (cheapest) machine that still finishes a job by a deadline. Faster machines obviously also make the deadline, and slower machines obviously miss it. So if you line up every machine speed from slow to fast, there is a single tipping point: everything to the right of it works, everything to the left fails.

That ordering is the whole game. You do not have to try every speed — you can bisect. Test a middle speed: if it makes the deadline, the answer is that speed or slower, so throw away the faster half; if it misses, the answer is faster, so throw away the slower half. Each test halves the candidates.

Walk through it

On the right, the cells are the candidate speeds 1 through 11. The lo and hi pointers bracket the live window; mid is the speed we are currently testing. At each mid we run a feasibility check — hours(k) = ceil(3/k) + ceil(6/k) + ceil(7/k) + ceil(11/k) — and compare it to the 8-hour budget, shown in the readout below the strip.

Watch the window shrink. At mid = 6 the job takes 6 hours (within budget), so 6 is feasible and we pull hi down to keep [1, 6]. At mid = 3 it takes 10 hours (over budget), so we push lo up to 4. Then mid = 5 works, and finally mid = 4 works — lo and hi collide at 4, the slowest speed that still finishes in time. Discarded speeds dim out; the final answer locks in green.

The code, line by line

import math
 
def min_eating_speed(piles, h):
    def feasible(k):                      # hours needed at speed k
        hours = sum(math.ceil(p / k) for p in piles)
        return hours <= h                 # finishes within budget?
 
    lo, hi = 1, max(piles)                # answer lives in [1, max]
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):                 # mid works...
            hi = mid                      # ...maybe slower works too
        else:                             # mid too slow
            lo = mid + 1                  # need a faster speed
    return lo                             # smallest feasible speed

• feasible(k) is the predicate. It does not find the answer — it only answers yes/no for one guess. Keeping it as a tiny helper is the cleanest way to write these problems.
• lo, hi = 1, max(piles) bounds the answer. Speed 0 is meaningless, and any speed above max(piles) clears every pile in one hour, so it can never be the minimum.
• hi = mid (not mid - 1): when mid works it is still a candidate for the smallest answer, so we keep it in the window.
• lo = mid + 1: when mid fails, mid and everything slower are hopeless, so we move strictly past it.
• The loop runs while lo < hi and returns lo when they meet — that converged value is the leftmost (smallest) speed for which feasible is true.

Complexity

Here n is the number of piles and m = max(piles) is the size of the answer range. We do about log m halvings, and each one runs feasible over all n piles — so O(n log m). Compare that to checking every speed one by one, which is O(n m).

When to use / pitfalls

Practice