Motivation
Binary search need not look for a key stored in an array. Sometimes the unknown answer is a number: a capacity, a permitted delay, or a maximum load. Trying one number answers a yes-or-no question. If every feasible number remains feasible when increased, those answers have a boundary that binary search can locate.
There are two separate proof obligations. First, prove that the yes-or-no test really answers the intended feasibility question. Second, prove that the search retains the first feasible value. A fast search around an incorrect test still returns an incorrect answer. We develop both arguments for partitioning a fixed sequence of nonnegative loads into consecutive blocks.
Definitions and model
Definition 1.3.1
(A monotone predicate and its boundary)
Let be an integer. A predicate on the integer indices is monotone here if implies whenever . Its boundary is the least true index, or if every index is false. Thus , all indices below are false, and all domain indices at least are true.
The predicate is fixed throughout the search: evaluating it must not change which future queries are true. An implementation may compute from an input rather than store a Boolean array. The integer is a boundary sentinel, not an index at which the search may evaluate .
Initially assume a word-RAM in which indices, interval differences and the required arithmetic fit in a constant number of words. Array access and arithmetic on those words take constant time. A call to has its own cost; it is not automatically one machine operation.
Boundary-search theorem
Theorem 1.3.2
(Find the first true index, including an absent boundary)
For every monotone on indices, the following algorithm returns . It makes at most predicate calls and uses constant auxiliary space apart from the predicate's workspace.
lo = 0
hi = N
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if P(mid):
hi = mid
else:
lo = mid + 1
return lo
The invariant records what has been ruled out
Proof
(Boundary search: invariant and termination)
Maintain , together with two statements: every domain index below is false, and every domain index at least is true. Equivalently, the unknown boundary satisfies . Initially the two outside regions are empty, so the invariant holds even for an all-false or all-true predicate.
If is true, monotonicity makes every later domain index true. Setting preserves the invariant and retains as a possible answer. If is false, no earlier index can be true: an earlier true value would force true. Setting therefore preserves the invariant. When the bounds meet, gives .
During an iteration, , so every query is in the domain. The nonnegative integer width strictly decreases; its new value is at most . After iterations it is at most . For , we have , so the width is zero. When , no iteration or query occurs and the algorithm returns zero.
Proof X-ray
A true midpoint stays a possible answer
The assignment does not say that the midpoint is wrong. It says that nothing strictly after it can be the first true index. The remaining possibilities for the answer are the closed integer interval , although every queried midpoint lies in the half-open index interval . Keeping these two roles distinct explains both the update and the sentinel .
If each predicate evaluation costs at most word operations and preprocessing costs , the total is . The logarithmic call count alone is not a logarithmic running-time theorem. The midpoint expression avoids adding the two endpoints, but the representation must still safely hold their difference and all other algorithm arithmetic.
A feasibility problem: consecutive load blocks
Let be nonnegative integers with , and let . A partition uses endpoints
Block consists of the consecutive entries with indices . Its load is their sum. Every entry must occur once, the input order is fixed, and blocks are nonempty. We want to minimize the largest block load. There are finitely many endpoint choices, so an optimum exists.
For an integer capacity , define to mean that some legal partition has every block load at most . A partition feasible at remains feasible at any larger capacity, so is monotone. This conclusion follows from the problem definition, before choosing an algorithm for testing it.
The greedy feasibility test
Scan from left to right, adding the next entry to the current block if it still fits. Otherwise, close the current block and start another one with that entry. Reject an entry larger than , since a nonnegative block containing it cannot have load at most .
feasible(B):
blocks = 1
load = 0
for x in a, in the original order:
if x > B:
return false
if load + x > B:
blocks = blocks + 1
load = x
else:
load = load + x
return blocks <= k
The test never creates an empty block. In particular, the first entry fits into the initially empty current block after the rejection check. Every block it constructs has load at most . Thus an accepted partition really is feasible. The harder direction is that a rejected input has no better placement of cuts.
Theorem 1.3.3
(The greedy test uses the fewest blocks)
If every , the greedy scan constructs a feasible partition with the minimum possible number of blocks. Consequently, feasible(B) returns true exactly when holds.
Proof by comparing reached endpoints
Proof
(Greedy endpoints never fall behind)
Let be the endpoint reached after greedy blocks, with ; after the scan has finished, define all later . Consider any feasible partition with endpoints . We prove for .
Suppose . If , the claim is already true because greedy endpoints do not decrease. Otherwise, the segment from to is a suffix of the other partition's th block. Nonnegative entries imply that this suffix has load no larger than that whole block, hence at most .
The greedy block starting at extends to the furthest feasible endpoint. Indeed, once the next addition exceeds , adding further nonnegative entries cannot restore feasibility. It must therefore reach at least . This proves the induction. At , , so greedy has finished in at most blocks. Since the competing feasible partition was arbitrary, greedy minimizes their number.
Proof X-ray
Where nonnegativity and the endpoint comparison enter
The induction compares what greedy has covered after blocks with what any feasible partition has covered after the same number of blocks; it never claims that the cuts coincide. Nonnegativity is used twice. First, the part of the competitor's th block that starts at is a suffix, and a suffix of a block of nonnegative entries has load at most the whole block, hence at most . Second, once the next entry pushes the current greedy load above , later entries cannot lower it, so a greedy block ends at the furthest feasible endpoint. The hypothesis guarantees that a greedy block starting before the end contains at least one entry. The induction closes at : means greedy has finished within blocks, whatever feasible the competitor used. With a negative entry the suffix property fails, and the counterexample below shows the scan rejecting a capacity that is feasible.
Searching for the optimal capacity
Compute
Every feasible capacity is at least , because the block containing a maximum entry has at least its load. Capacity is feasible by taking the entire sequence as one block. Therefore the optimum is an integer in .
Run the same loop with lo = L, hi = S and P(mid) = feasible(mid). Here the initial upper bound is already feasible, and the invariant is . Each branch follows from the proved predicate, so termination returns . No test of is needed. If , the loop makes no calls; the preprocessing still takes time.
One feasibility call scans entries in word operations and constant workspace. With , computing the bounds and searching takes
word operations. A final scan at records the greedy cut endpoints and provides a witness partition. It adds time and up to output words; the search itself needs only constant auxiliary words. The input array is excluded from that space bound.
Concept lensAlgorithmic
The greedy test as jumps along prefix sums
Let , a nondecreasing array with . When , a greedy block starting at endpoint ends at the largest with , and the test succeeds exactly when jumps reach . Each jump is itself a boundary search on the monotone predicate , so after preprocessing one test costs rather than .
What the arithmetic assumption permits
The word bound requires safe storage of , the indices and even an attempted sum load + x that exceeds the current capacity. With unbounded binary inputs these are not automatically unit-cost operations. If each entry has at most bits, bits suffice for these loads, attempted sums and counters. A simple binary implementation uses bit operations per addition or comparison and search iterations, giving an upper bound of bit operations, including preprocessing. This is a polynomial bound in binary input size, not an assertion that bit arithmetic is free.
Worked examples
Worked example 1.3.4
(Follow both the search and the feasibility scan)
For with , initially and . At , greedy gives and , so set . At midpoint , it needs , , , so set . Midpoint is feasible, giving ; midpoint needs three blocks, giving . The bounds meet at , with witness loads and . The last false capacity, , and monotonicity certify that no smaller capacity works.
Worked example 1.3.5
(Duplicates are boundary queries too)
In the sorted array , use defined by . Its first true index is one. Using instead gives index four. Their difference, three, is the number of occurrences of two. If no entry qualifies, the boundary is , which is a valid returned position rather than a valid array access.
Worked example 1.3.6
(Zero loads do not require positive capacity)
For and , . Search returns zero without a predicate call, and the witness scan uses the single block . The problem allows at most two blocks. Requiring exactly two would need an additional cut, although the optimum value would remain zero.
Common mistakes and counterexamples
Counterexample mode
Negative loads destroy this greedy proof
Take , , and . The whole sequence has load four, so one block is feasible. Greedy nevertheless closes its first block before the second four and uses two blocks. Once negative entries are allowed, a temporarily excessive prefix may become feasible later. The predicate defined by the existence of a partition is still monotone in ; this particular algorithm no longer computes it correctly.
Common mistake
(Applying the consecutive-block proof to reordered loads)
Order is another assumption, not a cosmetic restriction. For and , the best consecutive partition has maximum load , achieved by cutting after the second entry. If reordering is permitted, and give maximum load . A proof for consecutive blocks does not solve unrestricted assignment.
Common mistake
(Moving the lower bound to the midpoint)
Updating lo = mid on a false query can fail to terminate: with bounds zero and one, the midpoint is zero and the bounds need not change. The false midpoint is excluded, so the correct update is lo = mid + 1.
Common mistake
(Searching a predicate that is not monotone)
Each loop iteration may terminate and still discard the answer. For truth values [true, false, true], the algorithm first tests the middle index, finds it false and sets ; it then returns , although the first true index is . Monotonicity is what justifies every discarded region.
Summary
A boundary search is correct because a fixed monotone predicate justifies every discarded region. Turning optimization into feasibility adds another obligation: prove the decision procedure itself. For nonnegative consecutive loads, the greedy endpoint comparison supplies that proof, and binary search then finds the optimal capacity with only logarithmically many linear scans.
Exercises
Quick check
(Trace boundary search on [false, false, false]. What changes if all three values are true? Explain the result on an empty domain.)
Solution · Answer
Start at . The false query at one gives ; the false query at two gives , so return the sentinel three. With all values true, the queries at one and zero give and , so return zero. With , the loop is skipped and zero is again the boundary. No out-of-domain query is needed in any case.
Quick check
(Count the occurrences of a target in a sorted array using two boundary searches. Include the case where is absent.)
Solution · Answer
Find , the first index with , and , the first with , returning if the corresponding predicate is always false. Sortedness makes both predicates monotone. Precisely the indices in have value , so the count is . If is absent, the two boundaries coincide, including when both are .
Exercise 1.3.7
(Find the optimal capacity for with . Give a feasible partition and prove that a smaller capacity is impossible.)
Core
Solution(3)
- 1
Bound the capacity from below
Every feasible capacity is at least .
Because: The block containing the entry has load at least .
- 2
Exhibit a partition at capacity
Key step
The consecutive blocks , , have loads , , . All are at most , and there are three blocks, so holds.
- 3
Conclude that the optimum is
Capacity is feasible and no smaller capacity is, so . A full search trace is unnecessary for this certificate.
Quick check
(Explain exactly where nonnegativity enters the greedy proof. Why is monotonicity of alone insufficient to justify the scan?)
Solution · Answer
A suffix of a block has no larger load than the whole block only because the removed entries are nonnegative. Also, after the next entry makes a prefix exceed capacity, later nonnegative entries cannot bring its sum down. Monotonicity of the existence predicate justifies searching its boundary, but does not prove that any proposed oracle evaluates that predicate. The signed counterexample separates these two issues.
Exercise 1.3.8
(Under , prove that requiring exactly nonempty blocks has the same optimal capacity as allowing at most . What fails when ?)
CoreProof
Solution(3)
- 1
Start from a feasible partition with blocks
Since , some block contains at least two entries.
- 2
Split that block into two nonempty consecutive pieces
Key step
The new partition has blocks and the same maximum load bound. Repeat until exactly blocks exist.
Because: The entries are nonnegative, so each piece has load at most the load of the original block.
- 3
Compare the two optima
∎Every exactly- partition is also an at-most- partition, and the splitting shows the converse without raising the capacity, so the optima agree. If , exactly nonempty blocks are impossible, while at-most- partitions remain feasible.
Quick check
(Suppose a feasibility oracle costs per call. Does a binary search making calls have running time? State a justified upper bound, including preprocessing cost .)
Solution · Answer
Charge the cost of each call as well as loop overhead. For , the resulting upper bound is under the stated per-call and word-operation assumptions. The number of calls is logarithmic; the time spent inside them need not be. For ranges that may have size zero or one, use and include constant overhead.