Example - Capacity to Ship Packages

Problem: Ship packages over $D$ days. Find minimum capacity.

Approach: Binary search on capacity $[\max(weights), \sum(weights)]$. For each capacity, simulate loading and count days.

function shipWithinDays(weights, D):
    low = max(weights)
    high = sum(weights)
    while low < high:
        mid = (low + high) / 2
        if canShip(weights, mid, D):
            high = mid
        else:
            low = mid + 1
    return low

Time: $O(n \log(\sum weights))$. Space: $O(1)$.