Python binary search on capacity: prove the feasibility predicate

Operation contract

The packing rule keeps order and assigns each whole shipment to one day. The minimum possible capacity is the largest single shipment; the maximum is their total weight. For each midpoint the scan counts days needed. A feasible midpoint lowers the upper bound, while an infeasible one raises the lower bound. Three days need capacity five for the stated sequence.

Failure and ownership boundary

This is not bin packing: shipments are never reordered or split. A bad feasibility rule can invalidate the monotonic property and make binary search return nonsense. Python binary search: use a half-open interval and require sorted input, Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs and Python 0/1 knapsack: descending capacity prevents item reuse clarify the distinction.

Working program

def minimum_daily_capacity(weights, days):
    if type(weights) is not list or not 1 <= len(weights) <= 100 or any(type(weight) is not int or not 1 <= weight <= 1000 for weight in weights):
        raise ValueError("shipment weights")
    if type(days) is not int or not 1 <= days <= len(weights):
        raise ValueError("day count")
    def feasible(capacity):
        used, load = 1, 0
        for weight in weights:
            if load + weight > capacity:
                used += 1
                load = 0
            load += weight
        return used <= days
    low, high = max(weights), sum(weights)
    while low < high:
        middle = (low + high) // 2
        if feasible(middle):
            high = middle
        else:
            low = middle + 1
    return low

print(minimum_daily_capacity([3, 2, 2, 4, 1], 3))
try:
    minimum_daily_capacity([3, 2], True)
except ValueError:
    print("day count rejected")

Output

5
day count rejected

Costs and limits

Each feasibility scan takes O(n) time. Searching the integer range takes O(n log S) time for total weight S, with O(1) extra working storage beyond the input.

Common Mistakes

• Do not use this predicate if shipments may be reordered or split.
• Start the lower bound at the largest shipment.

Connected lessons

Python binary search: use a half-open interval and require sorted input, Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs, Python 0/1 knapsack: descending capacity prevents item reuse.