Seven of this site's other ten Searching entries answer the same question — does this exact value exist in the array — differing only in what's assumed about the data. Two more, Ternary Search and Quickselect, each answer a different question about an actual array: where a unimodal sequence peaks, and which rank an element holds. One more, Saddleback Search, answers the same value-exists question as the first seven, just on a matrix sorted along both axes instead of an array. This entry doesn't search an array at all either. Given a yes/no question that only gets easier to satisfy as some numeric parameter grows — a monotonic feasibility check — it binary-searches the space of possible answers themselves, the exact same halving trick aimed at a boundary between "no" and "yes" instead of a location inside a data structure.
The worked example below is the classic ship packages within D days problem: a
conveyor belt loads packages onto a ship in the given order, one day's worth at a time, and a
day's load can't exceed the ship's capacity. Given a fixed number of days D, find the
smallest capacity that still gets every package shipped within D
days. There's no array of candidate capacities sitting in memory to search — capacity can be any
integer from the heaviest single package (the hard floor; anything smaller can never load that
package at all) up to the sum of every package's weight (the trivial ceiling; that capacity ships
everything in one day). But "can this capacity finish in D days or fewer" only gets
easier to satisfy as capacity grows — never harder — so that entire range of integers is
binary-searchable exactly like a sorted array would be.
Each cell is one candidate capacity, not a package — the full row spans every integer from the heaviest single package up to the sum of all of them. Step through and watch the range close in on the smallest capacity that still ships everything within the given number of days.
The key fact isn't about the packages — it's about the shape of feasible(capacity)
itself: if some capacity c can already ship everything within D days,
every larger capacity can too (more room per day never makes a load harder to fit, and a load that
already fit inside fewer days still fits inside D). That means the boolean sequence
"is this capacity feasible," read in order from the smallest candidate to the largest, looks
exactly like false, false, …, false, true, true, …, true — never a stray
true before the switchover, never a stray false after it. That's the same
invariant plain Binary Search relies on for a sorted
array, just phrased over a feasibility check instead of an ordering:
if feasible(mid):
# mid works — the answer is mid or something smaller. Keep mid, discard everything above it.
hi = mid
else:
# mid doesn't work, and nothing smaller can either (feasibility only improves upward).
lo = mid + 1Each step still halves the range exactly like array-based binary search, and the loop still
ends with lo === hi pointing at the single boundary value — it's just that "the
array" here is the implicit list of integers from the floor to the ceiling, and the single
comparison per step (arr[mid] === target) is replaced by a whole function call
(feasible(mid)) that can do arbitrary work to answer one yes/no question.
function minCapacity(weights, days) {
function daysNeeded(cap) {
let d = 1, load = 0;
for (const w of weights) {
if (load + w > cap) { d++; load = w; }
else load += w;
}
return d;
}
let lo = Math.max(...weights); // floor: the heaviest single package
let hi = weights.reduce((a, b) => a + b, 0); // ceiling: everything in one day
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (daysNeeded(mid) <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}The predicate has to be monotonic in exactly the direction the search assumes — checking
the wrong condition breaks that silently, with no error and no crash. Suppose the question
were "does this capacity ship everything in exactly D days" instead of "D
days or fewer." That sounds like a reasonable, even more precise thing to ask — but it isn't
monotonic the way the search needs. On the ten-package, five-day example above, the true days-needed
figure falls from 7 at capacity 10 down to 1 at capacity 55, hitting exactly 5 only for capacities 15
and 16 — a narrow island in the middle of the range, with "not exactly 5" on both sides of
it, not a clean false-then-true split. Running the exact same lo/hi-narrowing
loop above with that predicate substituted in doesn't error or loop forever — it just converges
confidently on capacity 55 (which actually finishes in 1 day, nowhere near exactly
5) instead of the real answer, 15. Every probed midpoint along the way happens to fall on the "too
many days" side of the island, so the loop keeps raising lo past the island entirely
and lands on the ceiling, having never once evaluated a capacity where the exact-match predicate
was even true. Checked by running both predicates against the identical loop and comparing to a
brute-force scan of every capacity from 10 to 55: the "≤ D" predicate matches the brute-force answer
every time, the "== D" predicate returns a capacity that doesn't remotely satisfy the question it was
supposedly answering.
The midpoint formula and the branch direction have to agree, or the loop never
terminates. The reference implementation above always rounds mid down
(lo + Math.floor((hi - lo) / 2)) and, on success, narrows to hi = mid
(keeping mid itself as a still-live candidate). That combination is required: rounding
mid up instead (Math.ceil((lo + hi) / 2)) while still using hi =
mid on success looks like a harmless style choice, but once the range narrows to
lo = 14, hi = 15, the ceiling formula computes mid = 15 every single time —
feasible, so hi = mid sets hi to the value it already was. Neither pointer
ever moves again. Run it with a 100-iteration safety cap on the exact same ten-package, five-day
example and it hits the cap still stuck at lo = 14, hi = 15, having made zero progress
across the final 96 of those iterations — a genuine infinite loop, not a slow one, and nothing about
the output looks like an error while it's happening. Rounding down with hi = mid or
rounding up with lo = mid both work; mixing a round-up formula with the
hi = mid branch is the specific combination that fails.
The range from floor to ceiling shrinks by half every step, so the loop runs
O(log(range)) times — on the ten-package example, a range of 46 candidate
capacities takes at most 6 iterations, matching the demo above exactly. Each iteration calls
feasible once, and here that costs O(n) (one pass over the packages to
simulate a day's worth of loading), for a total of O(n log(range)) — dramatically
cheaper than checking every candidate capacity one at a time from the floor upward, which would cost
O(n · range) in the worst case. The technique itself doesn't care what
feasible checks; the packages-and-days example is one concrete instance of a much more
general shape — any question of the form "what's the smallest (or largest) parameter value for which
this yes/no check passes," as long as that check is verified monotonic first. Skipping that
verification is exactly what the first pitfall above is about. See Choosing a Search Algorithm for how this fits
alongside the site's other ten Searching entries.