Know this before you start: “Binary search on the answer (guess + check)”

Binary search on the answer

When “can it be done with x?” flips from no to yes as x grows, binary search over x itself, even if no array is sorted.

The idea

Some problems ask for the smallest speed, capacity or number of days that works. If you can quickly check one guess, and every value above a working one also works, the answers look like no, no, no, yes, yes.

Binary search over the range of possible answers to find the first yes. Each check might be O(n), giving O(n log range) overall.

See it step by step

Smallest eating speed to finish piles [3, 6, 7, 11] in 8 hours

Speeds 1…11 are possible. Hours at speed k = sum of ceil(pile / k).
k = 6 → 6 hours ✓, try smaller. k = 3 → 10 hours ✗, go bigger.
k = 4 → 8 hours ✓, k = 3 ✗ → the answer is 4.

In code (Python)

def min_speed(piles, hours):
    def finishes(k):
        return sum((p + k - 1) // k for p in piles) <= hours

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if finishes(mid):
            hi = mid          # works: maybe smaller works too
        else:
            lo = mid + 1
    return lo

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

O(n log m), m = the size of the answer range.

When you'll use it

“minimum speed / capacity / days / largest minimum distance” with an easy yes/no check.

Common mistakes

Choosing a range that doesn't contain the answer.
hi = mid − 1 after a success, which can skip it.