Binary search on the answer

A warehouse must ship parcels in their recorded order over a fixed number of days. It can choose where one day's batch ends, but it cannot split a parcel or move later parcels ahead. The question is the smallest daily weight capacity that can finish the work.

Guessing the batch boundaries directly creates many possibilities. Checking one proposed capacity is much easier: fill a day until the next parcel would exceed it, then start another day.

Choosing a daily shipping capacity

Find a minimum capacity while retaining input order and allowing at most a fixed number of contiguous groups. The answer space can be much larger than the number of weights.

Testing every integer capacity is correct but scales with the numeric answer range. Binary search needs a monotone feasibility predicate: once a capacity can complete the ordered partition, every larger capacity can too.

Asking whether a capacity is enough

With weights [2, 3, 4] and two days, capacity 4 needs three batches, while 5 permits [2, 3] | [4]. Any capacity above 5 also works. That false-then-true boundary is what binary search needs. Search between the heaviest parcel and the total weight, keeping a feasible midpoint as a possible answer rather than skipping past it.

The greedy feasibility scan fills the current group until the next weight would exceed capacity. If capacity works, every larger capacity works too. Binary search the first feasible capacity between the largest weight and the total, computing mid as low+(high-low)/2. Final O(n log(sum-max+1)) time and O(1) workspace.

Midpoint arithmetic should not overflow even when both bounds are individually valid:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long low = Long.MAX_VALUE - 10;
        long high = Long.MAX_VALUE - 2;
        long middle = low + (high - low) / 2;
        assert middle == Long.MAX_VALUE - 6;
        assert low <= middle && middle <= high;
    }
}

Adding the bounds before dividing can overflow. This safe midpoint is useful only after the feasibility invariant establishes what each bound means. Validate positive weights and days before evaluating that predicate.

Finding the first capacity that works

Binary search on a monotone answer appears in capacity planning, batching limits, and minimum feasible thresholds. It depends on a proof of monotonicity; a plausible-looking numeric parameter alone is not sufficient.

Return the smallest capacity dividing positive weights in their original order into at most days nonempty contiguous groups. Extra days may remain unused. Empty weights return zero for positive days. Reject days <= 0 or any weight <= 0.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

A larger working capacity would meet the deadline but overstate what the warehouse actually needs.