Binary search on the answer: when nothing is sorted but you can still binary search

Students learn binary search as "find x in a sorted array" and then get stuck on questions where nothing is sorted. The trick is that you are not searching the array. You are searching the answer.

The problem

You have packages with weights w[i] that must be shipped in order. A ship carries them over D days, loading packages in order each day until the next one would exceed its capacity. What is the minimum capacity that ships everything within D days?

Brute force

The capacity is at least max(w) (the heaviest package must fit) and at most sum(w) (ship everything on day 1). Try every capacity from max to sum, simulate, return the first that works. With sum up to 2.5 × 10^7 that is far too slow.

The observation

If capacity c works, then c + 1 also works. A bigger ship never needs more days. So the answers look like this:

capacity:  4  5  6  7  8  9  10 ...
works?     F  F  T  T  T  T  T  ...

That is a sorted array of booleans. Find the first T. That is binary search. The only thing you need is a function feasible(c) that answers yes or no in O(n).

bool canShip(const vector<int>& w, int days, long long cap) {
    int used = 1;
    long long load = 0;
    for (int x : w) {
        if (load + x > cap) { used++; load = 0; }
        load += x;
    }
    return used <= days;
}

int shipWithinDays(vector<int>& w, int days) {
    long long lo = *max_element(w.begin(), w.end());
    long long hi = accumulate(w.begin(), w.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canShip(w, days, mid)) hi = mid;   // mid works, maybe something smaller works too
        else lo = mid + 1;                     // mid fails, answer is bigger
    }
    return (int)lo;
}

Dry run

w = [3, 2, 2, 4, 1, 4], days = 3. lo = 4, hi = 16.

• mid = 10: [3,2,2] [4,1,4] = 2 days. Works, hi = 10.
• mid = 7: [3,2,2] [4,1] [4] = 3 days. Works, hi = 7.
• mid = 5: [3,2] [2] [4,1] [4] = 4 days. Fails, lo = 6.
• mid = 6: [3,2] [2,4] [1,4] = 3 days. Works, hi = 6.

lo == hi == 6. Answer 6.

How to recognise it

• "Minimize the maximum" or "maximize the minimum"
• "What is the smallest X such that you can finish within D days / K workers / H hours"
• Values up to 10^9, so you cannot loop over every candidate
• You can write the yes/no check in O(n) or O(n log n)

The three bugs everybody makes

1. Wrong bounds. Starting lo at 1 instead of max(w) makes the check do strange things. Think about what the smallest possible answer is.
2. Overflow. Sums of 10^5 values up to 10^9 do not fit in int. long long, always.
3. Infinite loop on max-of-min questions. In aggressive cows you search for the largest value that works, so the update becomes lo = mid. With mid rounded down and lo + 1 == hi, lo never moves. Use mid = lo + (hi - lo + 1) / 2 there.

Same pattern: Koko eating bananas (search the speed), split array largest sum (literally this question in disguise), minimum days to make m bouquets, aggressive cows / magnetic force between balls (maximize the minimum).

Time: O(n log(sum)). For n = 5 × 10^4 and sum around 2.5 × 10^7, that is about 25 checks of 5 × 10^4 each, roughly 1.25 million operations. Space: O(1).