Search a boundary in the answer space
Weights one, two, three, four and five must ship in that order within three days. Each day has capacity C, packages are indivisible, and their order cannot change. Find the smallest feasible integer capacity. We are not searching for an existing array element. We ask a decision question about candidate answers and locate the first candidate that succeeds.
Increasing capacity preserves any packing that already worked, so it cannot increase the minimum required days. This monotonic feasibility boundary is the foundation of binary search on answers. Numeric candidates alone are insufficient. Establish that relaxing the candidate cannot make a previously valid solution invalid under the actual task contract, including ordering, splitting and deadline requirements.
Build a correct decision procedure
At capacity six, ship one, two and three on day one, four on day two and five on day three. Capacity five requires four days: one with two, then three, four and five separately. The decision routine scans in order and starts a new day only when the next package would overflow. These adjacent feasible and infeasible candidates establish that six is the boundary for this example.
For ordered nonnegative packages, filling each day as far as possible does not hurt later choices. Ending a day earlier leaves at least as much remaining work without gaining capacity on later days. Justify this greedy decision separately from the outer binary search. A flawless boundary loop cannot rescue a decision predicate that answers the wrong feasibility question.
| Capacity | Daily groups | Within three days? |
|---|---|---|
| 5 | [1,2] / [3] / [4] / [5] | No: four days |
| 6 | [1,2,3] / [4] / [5] | Yes: three days |
Keep the answer inside a declared interval
For nonempty input, start lo at the largest weight and hi at the total weight. A smaller capacity cannot fit every individual package, while the total fits in one day when D is positive. Lo may already be feasible, so it is not an infeasible sentinel. The invariant is that the minimum feasible answer lies in the closed interval from lo through hi.
When mid succeeds, keep it as a candidate by setting hi to mid. When it fails, discard it and every smaller capacity by setting lo to mid plus one. Repeating only while lo is below hi strictly reduces the interval. Do not combine fragments from a sentinel-based implementation with these closed-interval updates; boundary conventions form one coherent argument.
Check small inputs against exhaustive candidates
The code rejects negative weights and nonpositive day counts. Empty input returns capacity zero, and zero-weight packages are permitted. If every weight is zero, both bounds start at zero and the search ends immediately. The helper reports an infeasible day count when one package cannot fit, although the chosen lower bound prevents such candidates in the ordinary search.
Tests enumerate short arrays with weights zero through two and several day limits. A reference tries every capacity from the largest weight to the total and takes the first feasible one. This checks boundary and interior values without reusing the binary-search loop. Small exhaustive evidence complements the invariant; neither a single large successful example nor fast timing alone establishes correctness.
from itertools import product
def days(weights,capacity):
used=1;load=0
for w in weights:
if w>capacity:return len(weights)+1
if load+w>capacity:used+=1;load=0
load+=w
return used
def capacity(weights,D):
if D<1 or any(w<0 for w in weights):raise ValueError('invalid inputs')
if not weights:return 0
lo=max(weights);hi=sum(weights)
while lo<hi:
mid=(lo+hi)//2
if days(weights,mid)<=D:hi=mid
else:lo=mid+1
return lo
assert capacity([1,2,3,4,5],3)==6
for n in range(1,6):
for weights in product(range(3),repeat=n):
for D in range(1,4):assert capacity(weights,D)==next(c for c in range(max(weights),sum(weights)+1) if days(weights,c)<=D)
assert capacity([],3)==0
print('example minimum=6; exhaustive small-capacity checks passed')
Include the cost of one predicate call
If the integer candidate interval has width U, binary search makes O(log(U plus one)) decisions. Each decision scans n packages, giving O(n log(U plus one)) time under the chosen arithmetic model. Writing O(log n) confuses the number of packages with the range of possible capacities. Include the initial maximum and sum scans as well.
Arbitrary-precision values introduce arithmetic costs, while fixed-width ports must avoid overflow in sums and midpoint computation. A decision can stop early once it exceeds D days, but that does not necessarily improve its worst-case scan bound. Distinguish an observed early exit on one workload from the asymptotic bound over all permitted inputs. The outer technique only multiplies the cost of a correct decision procedure; it does not make that cost disappear.
Separate monotonicity from the decision implementation
Requiring every used day to be filled exactly to capacity changes feasibility. Successful capacities may no longer form one uninterrupted suffix of the candidate range. Minimizing a tariff with capacity-dependent prices is also a different objective from minimizing capacity. State both the predicate and the optimization target before selecting a search strategy.
Allowing package reordering may preserve monotonic capacity feasibility while invalidating this particular in-order greedy decision routine. That distinction is important: monotonicity of the real problem and correctness of the implemented predicate are separate requirements. Revisit the decision proof whenever ordering, splitting or daily constraints change, even when the outer binary-search code still looks reusable. The same loop can efficiently locate the wrong boundary if its predicate models a different task.
Test the predicate as well as the final boundary
A returned minimum should be feasible and its preceding in-range candidate infeasible. But if both checks use the same defective predicate, they can share its error. For tiny inputs, an independent enumeration of allowed day boundaries can additionally validate the minimum-day decision itself. The supplied full-capacity reference checks the binary-search boundary, while the greedy-packing argument explains the predicate.
Different per-day capacities or incompatible package combinations can invalidate that predicate without changing the outer search code. Separate input normalization, feasibility and boundary search. That division shows which assumption must be revisited when requirements change, and prevents a passing old boundary test from being mistaken for verification of a newly different packing problem.
Exercise: show the feasible answer and its neighbor
For weights two, two, three and two days, the minimum capacity is four. Ship the first two packages together, then the final three. Capacity three needs three days, so the immediately smaller candidate fails. Give both a valid packing and the failed decision trace, rather than only a numeric answer.
With one allowed day, the answer becomes the total seven. With at least three days, it falls to the largest individual weight, three. Predict the direction of the answer before running the variation. Explain the candidate boundary, search invariant, one decision call and total computational cost separately. Those four pieces transfer to other optimization problems more reliably than copying the final binary-search loop without its feasibility argument.