ZERO / HERO
Guessing the right shoe size

Binary Search on the Answer

The analogy

You cannot compute the answer directly, but given any candidate you can check whether it works. So guess a size: too small? Guess bigger. Works? Try smaller and see if it still works. You are binary searching over possible answers rather than over an array.

Visualizer

Binary searching the answer

step 1 / 12
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
15
15
16
16

Ship [3, 2, 2, 4, 1, 4] in 3 days. What is the smallest daily capacity that works? We cannot compute it directly — but given any capacity we can CHECK it.answer space: 4..16

def min_capacity(weights, days):
    def check(cap):                  # monotone in cap
        used, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                used, cur = used + 1, 0
            cur += w
        return used <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                 # feasible: try smaller
        else:
            lo = mid + 1             # infeasible: need bigger
    return lo

# O(n log(sum)) — the check is the algorithm,
# the binary search is just the wrapper
Check yourself

What single property must check(x) have for this to be valid?