Binary Search on the Answer

Sometimes you binary search the answer value (capacity, time, k), not an index. You need: (1) a search range [lo, hi] of answers, (2) check(x) that is monotone so first feasible x can be found.

Try this in Python

def min_capacity(weights: list[int], days: int) -> int:
    def can(cap: int) -> bool:
        need, cur = 1, 0
        for w in weights:
            if w > cap:
                return False
            if cur + w > cap:
                need += 1
                cur = 0
            cur += w
        return need <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(min_capacity([1, 2, 3, 4, 5], 3))

Key takeaways

• check(x) should be cheap enough vs brute force.
• Prove monotonicity: if cap works, larger cap also works (typical).
• Narrow hi using obvious upper bounds first.