Binary Search on the Answer

Search over possible answers

If you can check "is answer x feasible?" and feasibility is monotonic (if capacity 15 works, 16 works too), binary search the answer range instead of the input. Typical problems: minimum ship capacity, minimum eating speed, smallest maximum subarray sum when splitting. Complexity is O(n log range), where each check is a greedy O(n) pass.

Minimum ship capacity, run

I ran this with Python 3.12.3 (standard library only). The search starts between the heaviest package and the total weight and finds capacities 15, 6 and 3 for the three test cases.

# Binary search on the answer: minimum ship capacity to deliver in D days
def days_needed(weights, cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days, load = days + 1, 0
        load += w
    return days

def ship_within_days(weights, D):
    lo, hi = max(weights), sum(weights)  # answer lies in this range
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= D:
            hi = mid                     # feasible: try smaller
        else:
            lo = mid + 1
    return lo

print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))
print(ship_within_days([3, 2, 2, 4, 1, 4], 3))
print(ship_within_days([1, 2, 3, 1, 1], 4))

Output:

15
6
3

Set the bounds carefully

The lower bound must be feasible-or-not and the upper bound must be feasible; here max(weights) and sum(weights).

Quick check: What property makes binary search on the answer valid?

• The array has no duplicates
• The input is sorted
• The answer is always an even number
• Feasibility is monotonic in the answer