Binary search on the answer

You’ll recognise it when

• The question asks for the smallest speed, capacity, time or budget that still works, or the largest distance or size that’s still possible.
• Checking one guess is easy: “at speed 7, how many hours?” is a simple loop, even though “what’s the best speed?” isn’t.
• If a guess works, every bigger guess works too (or every smaller one, for “largest” questions).
• The phrases minimise the maximum or maximise the minimum appear.

It’s the same loop as binary search over a sorted array. The difference is that there’s no array: each “element” is computed on demand by a check function.

The idea

You’re packing for a move and want to rent the smallest van that gets everything across town in three trips. You can’t work out the size from a formula, but you can take any van size and quickly test it: load in order, count the trips. If a 10 m³ van needs four trips, every smaller van needs at least four as well, so you never have to try those. If a 16 m³ van manages in three, so does every bigger one. Test the middle size each time, and every test rules out half of the sizes left.

That’s the whole trick. Line up the possible answers and write the check result under each: no, no, no, …, yes, yes, yes. The check is monotonic: it flips from no to yes exactly once. You want the first yes, and a sorted row of no’s and yes’s is exactly what binary search is good at.

How it works

Our problem: Koko has piles of bananas and h hours. Each hour she picks one pile and eats up to k bananas from it; if the pile has fewer, she finishes it and waits for the next hour. What’s the slowest speed k that finishes every pile within h hours? At speed k, a pile of p takes ⌈p / k⌉ hours, so checking one speed is a single loop over the piles.

Scroll through the steps and the graphic follows along. The bars are the piles; the row underneath is every candidate speed, with what we know about each. You can also edit the piles and h, or roll a random input.

Why it’s correct: every speed below lo is known to be too slow, and hi is known to fit. Each step keeps both facts true and shrinks the gap, so when lo meets hi it sits exactly on the first speed that fits.

def feasible(piles, h, speed):
    """Can Koko eat every pile within h hours at this many bananas per hour?"""
    hours = 0
    for p in piles:
        # A pile of p takes ceil(p / speed) hours; a part-hour counts as a whole one.
        hours += (p + speed - 1) // speed
    return hours <= h


def min_eating_speed(piles, h):
    """Slowest speed that finishes every pile in h hours. Needs h >= len(piles)."""
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(piles, h, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

#include <algorithm>
#include <vector>
using namespace std;

// Can Koko eat every pile within h hours at this many bananas per hour?
bool feasible(const vector<long long>& piles, long long h, long long speed) {
    long long hours = 0;  // 64-bit: the sum can pass 2^31 when speed is small
    for (long long p : piles) {
        // A pile of p takes ceil(p / speed) hours; a part-hour counts as a whole one.
        hours += (p + speed - 1) / speed;
    }
    return hours <= h;
}

// Slowest speed that finishes every pile in h hours. Needs h >= piles.size().
long long minEatingSpeed(const vector<long long>& piles, long long h) {
    long long lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(piles, h, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

class KokoBananas {
    // Can Koko eat every pile within h hours at this many bananas per hour?
    static boolean feasible(int[] piles, long h, long speed) {
        long hours = 0;  // long: the sum can pass 2^31 when speed is small
        for (int p : piles) {
            // A pile of p takes ceil(p / speed) hours; a part-hour counts as a whole one.
            hours += (p + speed - 1) / speed;
        }
        return hours <= h;
    }

    // Slowest speed that finishes every pile in h hours. Needs h >= piles.length.
    static long minEatingSpeed(int[] piles, long h) {
        long lo = 1, hi = 0;
        for (int p : piles) hi = Math.max(hi, p);
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (feasible(piles, h, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Every problem of this kind has the same shape. Only feasible and the range change:

lo, hi = smallest_possible, largest_possible   # hi must be feasible
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid          # mid works; maybe something smaller does too
    else:
        lo = mid + 1      # mid fails, and so does everything below it
return lo

Choosing the range. lo should be a value that could be the answer, and hi one that surely is feasible. Pick them from the problem: here nothing below 1 makes sense, and max(piles) always fits. For shipping packages, the capacity must hold the heaviest package (lo = max(w)) and never needs more than all of them at once (hi = sum(w)). A loose range is fine: doubling it costs one extra check.

Why monotonic matters. The loop never looks at the speeds it skips. That’s only safe if one test tells you about a whole block of them, which is exactly what “if k fits, every k' > k fits” gives you. If the check could go yes, no, yes, the search would land on some boundary, not necessarily the first one.

Why it’s O(n log m)

The range starts with m = max(piles) values and each loop halves it, so there are about log₂ m checks. Each check walks the n piles once. That’s O(n log m) time and O(1) extra space.

Trying every speed from 1 up would be O(n·m): up to 10¹³ steps for the second row.

Common mistakes

int hours = 0;         // ✗ wraps around; a too-slow speed can look like it fits
long long hours = 0;   // ✓ 64-bit total

hours += p // k                 # ✗ 7 bananas at 2/hour is 4 hours, not 3
hours += (p + k - 1) // k       # ✓ ceiling, exact

lo, hi = 1, sum(w)          # ✗ too-small capacities "work" if feasible never checks w <= cap
lo, hi = max(w), sum(w)     # ✓ every candidate can carry every package

mid = (lo + hi) // 2       # ✗ with lo = mid, loops forever on [3, 4]
mid = (lo + hi + 1) // 2   # ✓ always makes progress

Variations

• Ship packages within D days. Search capacities from max(w) to sum(w). The check loads packages in order and starts a new day whenever the next one would overflow; it fits if that takes at most D days.
• Split array, largest sum. Split an array into k contiguous parts so the biggest part sum is as small as possible. It’s the shipping check again: guess a limit, cut greedily, and count the parts.
• Maximise the minimum distance. Place c items (the “aggressive cows” problem) in sorted positions so the closest pair is as far apart as possible. Guess a gap d, place greedily from the left, and check you placed c. Small gaps work and big ones don’t, so search for the last yes with the round-up mid.
• Real-valued answers. When the answer is a real number (a time, a ratio), set lo = mid or hi = mid and run a fixed number of rounds, say 100, instead of while lo < hi. Each round halves the gap, so 100 rounds is far beyond double precision.
• Counting instead of checking. “The k-th smallest value” in a sorted matrix or a multiplication table: guess x, count how many values are <= x, and search for the first x whose count reaches k.