Binary search on the answer

Reach for it when

• Split array into k parts minimising the largest sum
• Koko eating bananas / capacity to ship packages
• Smallest divisor given a threshold
• Any 'can we do it in X?' where X monotonically gets easier

Reference implementation

def min_capacity(weights: list[int], days: int) -> int:
    def feasible(cap: int) -> bool:
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used <= days

    # Any valid capacity must hold the biggest single item.
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid           # mid works, try smaller
        else:
            lo = mid + 1
    return lo

Complexity: O(n log R) where R is the range of candidate answers.

What goes wrong

• Setting `lo = 0` when the answer must be at least max(weights) — the predicate then never holds.
• Writing `hi = mid - 1` in a lower-bound search, which skips the answer.
• A predicate that is not actually monotone — binary search is invalid and the bug looks random.

Practise on

• Capacity To Ship Packages Within D Days
• Koko Eating Bananas
• Split Array Largest Sum
• Find the Smallest Divisor Given a Threshold