Some optimization problems are easier to ask as yes-or-no questions. Instead of guessing the best capacity, ask whether a proposed capacity can process the input; then search the ordered capacities. The binary search is only as valid as two facts beneath it: feasibility must be monotone, and the test must be correct.
1. The optimization problem
A nonempty sequence of jobs has nonnegative integer sizes . Partition it, in its original order, into at most nonempty contiguous batches. The load of a batch is the sum of its jobs. Find the smallest integer such that every batch has load at most .
The contiguity condition matters: jobs cannot be reordered or split. Put and . Every feasible is at least , because the largest job must fit. Capacity is feasible with one batch, even when some sizes are zero. Thus an answer exists in . If , “at most ” does not require empty batches; a partition into singleton batches is allowed.
Definition 15.1.1
(Feasible capacity)
For sizes and a limit , an integer is feasible if the sequence can be cut, in its original order, into at most nonempty contiguous batches whose loads are all at most . The answer to the problem is the least feasible integer.
Proposition 15.1.2
(Feasibility is upward closed)
If is feasible and , then is feasible. Consequently the set of feasible integers is an interval whose least element is the answer.
Proof
(The same partition works)
A partition into at most nonempty contiguous batches with every load at most also has every load at most . So the same partition certifies . A set of integers closed under taking larger integers and containing the feasible has a least element, and it is exactly the set of integers from that element upward. ∎
This is an upward-closed predicate, so the desired answer is its first true integer. Binary search relies on this fact.
2. Greedy feasibility
For a proposed nonnegative capacity, scan from left to right. Start a new batch exactly when adding the next job would exceed :
feasible(a, k, C):
batches = 1
load = 0
for x in a:
if x > C: return false
if load + x > C:
batches += 1
load = x
else:
load += x
return batches <= k
The input is nonempty, so the first batch contains a job: with and the initial load + x > C test cannot start an empty batch. A zero-size job may join a full batch. Each constructed batch has load at most . The result is true precisely when the greedy batch count is at most .
Proposition 15.1.3
(The greedy test decides feasibility)
Let , and an integer . The procedure feasible(a, k, C) returns true if and only if is feasible.
Proof
(Greedy stays at least as far right)
If the test returns true. Every batch the procedure builds is nonempty, because a new batch is opened only with a job already placed in it. Each load is at most , and there are at most batches, so is feasible.
If is feasible. Take a partition into nonempty contiguous batches of load at most . If some job exceeded , its batch would have load at least that job, because sizes are nonnegative; so every and the test never returns false inside the loop. Let be the number of jobs covered by the first batches of this partition, with and , and let be the number covered by the first greedy batches, with and capped at . We show for .
For both are . Assume . If there is nothing to prove. Otherwise , and jobs form a suffix of the other partition's batch . Sizes are nonnegative, so their sum is at most that batch's load, hence at most . Along a run of nonnegative jobs the load never decreases, so greedy's batch , which stops at the first job that would overflow, extends over the longest run starting at job with load at most . That run includes job , so .
At we get , so greedy finishes within batches and returns true. ∎
Proof X-ray
Where nonnegativity and the limit enter the greedy proof
The non-obvious move is the comparison : greedy is not shown to match the optimal partition batch by batch, only to stay at least as far to the right after every batch. That is a stronger statement than the final count, and it is what makes the induction close.
Nonnegativity is used twice, in two different places. First, it makes the load nondecreasing along a run, so that cutting at the first overflow gives the longest run and the greedy batch cannot stop early. Second, it makes a suffix of a batch no heavier than the whole batch, so the stretch from to fits. The limit is used only at the very end, to compare the batch count with ; the capacity is fixed throughout, and monotonicity in plays no part in this proof. It is the binary search, not the greedy test, that needs the previous proposition.
The next block shows why nonnegativity cannot be dropped.
Counterexample mode
Greedy fails when sizes may be negative
Claim: the greedy test is correct for integer sizes of any sign. Take , , . The single batch has load , so is feasible. The procedure sets , then meets , where , so it opens a second batch and finally reports two batches, which exceeds . It returns false for a feasible capacity. The longest-run argument fails because a prefix of the batch, , has load even though the whole batch fits. With nonnegative sizes no prefix of a batch can be heavier than the batch, which is the property the proof uses.
3. Find the first feasible integer
Use the bounds and preserve the invariant that the answer lies in :
lo = max(a); hi = sum(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(a, k, mid): hi = mid
else: lo = mid + 1
return lo
When mid is feasible, the answer is at most mid; otherwise monotonicity says it is strictly larger. The interval shrinks to a single feasible answer. At most feasibility calls are needed; if no calls are needed. Reading the array and finding its bounds still costs , so the whole cost is arithmetic operations and storage for the retained array. For arbitrary-precision integers, arithmetic bit cost is separate.
Worked example
Worked example 15.1.4
(Two capacities around the optimum)
Let and . Here , .
- At , greedy produces , , , : four batches, so it is infeasible.
- At , greedy produces , , : three batches, so it is feasible.
Since 6 is infeasible and 7 is feasible, monotonicity proves that the optimum is 7. Listing one feasible arrangement alone would not exclude capacity 6.
Worked example 15.1.5
(The whole binary search on the same input)
Keep , , so and . The first midpoint is . At greedy gives with load , then with load : two batches, feasible, so . Next , feasible by the previous example, so . Then , infeasible, so . Now and the answer is , after three feasibility calls, within the bound .
Worked example 15.1.6
(Zero sizes and a generous limit)
First take and . Then , so and no feasibility call is made: the answer is , with one batch (or three singleton batches; no empty batch is needed). Next take and , so , . At , greedy puts , then (load ), then would give , so it ends with , : two batches, feasible, so . At the zero job joins the full batch, since , and greedy again gives , : feasible, so . The answer is .
4. Arithmetic and meaning of the answer
The expression lo + (hi - lo) // 2 avoids adding two potentially large nonnegative endpoints, but it does not make the input sum safe automatically. Choose a type that represents and every addition such as load + x; promote before arithmetic. The loop above assumes exact integer arithmetic and a fixed input throughout the search.
Common mistake
(Closing a batch when the load reaches the capacity)
Writing the test as load + x >= C opens a new batch even when the job fits exactly. For , , the loads are , then , so a second batch is opened and the test returns false. But is one batch of load , so is feasible. A batch may be filled to the capacity; only a strict overflow forces a cut.
Common mistake
(Summing in a type that is too small)
The loads and the upper bound are sums, not single sizes. With jobs of size , , which exceeds the largest signed 32-bit integer . Computing sum(a) or load + x in a 32-bit type wraps around, so the search starts from a wrong hi. Use a type that holds before any addition.
Checklist. State nonnegativity, ordering, contiguity and whether the limit is “at most” or “exactly” . Prove the greedy predicate, establish an actual feasible upper bound, justify monotonicity and bounds, and account for the magnitude of the sum. A different objective or negative inputs need a new proof.
Quick checks
Quick check
(Why can the search start at rather than ?)
Solution · Answer
The largest job lies in some batch, and sizes are nonnegative, so that batch has load at least . Any feasible capacity is therefore at least , and no capacity below can be the answer.
Quick check
(For and , is feasible? What is the answer?)
Solution · Answer
At greedy gives , , : three batches, so is infeasible. At it gives and : two batches, feasible. By monotonicity the answer is .
Quick check
(If , what is the answer, and why?)
Solution · Answer
The answer is . Capacity is feasible, because singleton batches are allowed and each has load at most ; and no capacity below is feasible.