Binary Search as a Boundary‑Finding Tool

Binary search is often introduced as a way to find a number in a sorted array. That is a useful starting point, but the more reusable question is: where does a sequence of answers change from false to true?
My binary search foundations article deals with exact matches, and my first and last position walkthrough applies lower and upper bounds to duplicate values. Here I want to concentrate on the part those loops rely on: designing a trustworthy yes‑or‑no question, choosing a finite search range, and accounting for the cost of answering it.
The candidates don't need to be stored in an array. They might be capacities, time limits, or integer budgets. What matters is that increasing the candidate cannot turn a successful answer back into a failure. Without that property, halving the range is merely throwing away possibilities with confidence.
Establish Monotonicity Before Writing the Loop
LeetCode's Capacity To Ship Packages Within D Days problem asks us to ship packages in their original order within a fixed number of days. Each package has a positive integer weight, and one day's load cannot exceed the chosen capacity. We may finish in fewer days, but we cannot split a package or rearrange the sequence.
Ask whether a particular capacity is sufficient. If capacity c works, any larger capacity also works: we can reuse the exact same daily grouping. The predicate therefore changes from false to true at most once. That is the monotonicity proof, and it exists independently of our implementation.
Now contrast "does this capacity use exactly three days?" That answer can become true and then false again as capacity grows enough to finish in two days. The wording of the predicate has changed the mathematical property. An apparently minor product requirement can make the same binary‑search loop invalid.
I start by writing this implication in plain language. It is easier to challenge before it has disappeared behind a helper called isValid, which tends to inspire more confidence than its name has earned.
A Helper with an Excluded Endpoint
The generic helper below searches integer candidates in [start, end). It returns the first true candidate, or end if none qualifies. It never calls the predicate at end, so that excluded endpoint can act as a sentinel rather than a real candidate.
Its preconditions are a non‑decreasing false‑to‑true predicate, safe integer endpoints with a safely representable difference, and start <= end. The shipping wrapper supplies those conditions. The generic helper does not validate an arbitrary callback or prove that its answers remain stable.
const firstTrue = (
start: number,
end: number,
predicate: (candidate: number) => boolean,
): number => {
let low = start;
let high = end;
while (low < high) {
const middle = low + Math.floor((high - low) / 2);
if (predicate(middle)) high = middle;
else low = middle + 1;
}
return low;
};
const minimumCapacity = (weights: readonly number[], days: number): number => {
if (!Number.isInteger(days) || days < 1) throw new Error('Days must be a positive integer');
if (weights.length === 0) return 0;
let largest = 0;
let total = 0;
for (const weight of weights) {
if (!Number.isSafeInteger(weight) || weight <= 0) throw new Error('Weights must be positive integers');
largest = Math.max(largest, weight);
total += weight;
}
if (!Number.isSafeInteger(total + 1)) throw new Error('Total is too large');
const canShip = (capacity: number): boolean => {
let usedDays = 1;
let load = 0;
for (const weight of weights) {
if (load + weight > capacity) {
usedDays++;
load = 0;
}
load += weight;
}
return usedDays <= days;
};
return firstTrue(largest, total + 1, canShip);
};Positions below low have been ruled false. Positions at or above high have been ruled true if they are real candidates. The unresolved interval lies between them. A true midpoint becomes the new excluded high endpoint because an earlier true candidate might exist. A false midpoint is discarded by moving low to the following integer.
When low and high meet, there are no unresolved candidates. Their common value is the first true candidate or the sentinel. An empty input range returns its end without evaluating the predicate, and an all‑false range returns the same sentinel after exhausting the candidates.
The Predicate Needs Its Own Proof
For a proposed capacity at least as large as the heaviest package, canShip greedily loads each day until the next package would exceed that capacity. It then starts another day. This produces the minimum number of days for that capacity under the fixed‑order rule.
To see why, compare the first day's endpoint with any valid grouping. Greedy takes the longest prefix that fits. No valid first day can end later, because adding another positive weight would exceed capacity. Starting the remaining work no earlier cannot help another grouping finish in fewer days. Applying the same argument to each remaining suffix establishes the greedy result.
That proof is separate from monotonicity. The question "does some grouping fit?" is monotone, but an incorrect implementation of the question could still make binary search return the wrong answer. There are two algorithms to verify here: the feasibility check and the interval search.
The search starts at the largest individual weight, since anything smaller cannot carry that package. It ends one past the total weight. The total itself is feasible in one day, so a non‑empty valid input always has a qualifying candidate inside the range. We don't need to test an impossible sentinel as though it were a capacity.
Walk through a Capacity Rather than an Index
Take weights [3, 2, 2, 4, 1] and a limit of three days. Capacity four needs four days: three, then two plus two, then four, then one. Capacity five uses three days: three plus two, then two, then four plus one.
The minimum is therefore five. The initial candidate range runs from four through twelve, represented by endpoints four and thirteen. The midpoint eight works, so the excluded high endpoint becomes eight. Six works too, followed by five. Four fails, advancing the low endpoint to five, where the search finishes.
Notice that the predicate scans package weights, not a precomputed table of capacities. The numeric candidate space can be much larger than the input array, but we only evaluate a logarithmic number of candidates. This is the useful connection to my Koko Eating Bananas article, where eating speed is the candidate and required hours supply the predicate.
Numeric Bounds are Part of Correctness
The challenge allows at most 50,000 packages, each weighing at most 500, so its total is at most 25 million and comfortably within exact integer arithmetic. The wrapper also rejects non‑positive or non‑integer weights and invalid day counts. It also checks that total + 1 is a safe integer. That protects the exclusive endpoint and ensures the non‑negative search interval and midpoint arithmetic stay within exact integer representation for these inputs.
Using a bitwise midpoint would convert values to a narrower integer representation and could break larger capacities. The distance‑based Math.floor expression avoids that conversion. It still requires a safely representable interval; writing a familiar expression is not a substitute for checking the numeric domain.
A bigint version would need a consistently different numeric representation, including its midpoint division and predicate arithmetic. A continuous search over fractional capacities would need a stopping tolerance or bounded iteration count instead of integer endpoint equality. Neither is a drop‑in tweak to this helper.
The empty weight list returns zero as an explicit extension of the example. For non‑empty lists, returning zero would violate the heaviest‑package lower bound. Making that exceptional input visible is clearer than hoping it falls out of an initial maximum calculation.
Count Predicate Work, Not Just Probes
If the candidate range contains R integers and a predicate evaluation costs C, binary search takes O(C log(R + 1)) time, plus setup. Here the predicate scans n weights, so the complete algorithm takes O(n log(R + 1)) time and O(1) auxiliary space.
A logarithmic number of expensive database queries can still be expensive. A predicate that changes its answer because external data mutates during the search can also violate the assumptions entirely. The helper expects a stable question over one consistent input, not a series of unrelated snapshots.
I would cache repeated expensive subcomputations only after identifying what remains unchanged across candidates. Caching the wrong thing can accidentally make the predicate depend on which midpoint was tested first, which is a very inventive way to lose monotonicity.
Test the Question and the Search Separately
For the generic helper, enumerate every possible false‑to‑true transition in small integer ranges, including all‑true, all‑false, and empty ranges. The expected answer is known directly from the chosen transition. Check that every predicate call stays within the supplied range.
For shipping, enumerate small package arrays and compare the result against a reference that tries every possible division into contiguous daily groups. That reference checks the greedy predicate rather than repeating it. Also verify minimality explicitly: the returned capacity works, and one less fails when it remains inside the meaningful domain.
The useful reusable idea is not a universal binary‑search template. It is a sequence of obligations: define the candidate domain, prove the predicate's direction, implement that predicate accurately, and give the sentinel a clear meaning. Once those are settled, the loop is the least mysterious part.