Binary Search on the Answer: Turning Feasibility into Optimization

Binary search is usually introduced as a way to find a value in a sorted array. Its more general form does not need an array at all. It needs an ordered answer domain and a predicate whose truth changes at most once. That is enough to turn many optimization problems into repeated yes-or-no decisions.

Suppose a system must choose the smallest processing capacity that meets a deadline. Computing the optimum directly may be awkward, but checking one proposed capacity can be easy: simulate the schedule and ask whether it finishes in time. If every capacity above a feasible one is also feasible, the answers look like false, false, ..., true, true. Binary search locates the boundary.

The thesis is simple: binary search on the answer is a proof technique before it is a loop template. Correctness depends on defining feasibility, proving monotonicity, bracketing the transition, and stating what each boundary means. This article develops that method for integers, extends it cautiously to floating point, and shows how to test the failure modes that often survive happy-path examples.

Reframe an Optimum as a Decision Boundary #

An optimization problem asks for a minimum or maximum. A decision problem asks whether a candidate satisfies a condition. Binary search connects them when the decision answers are monotone over an ordered domain.

For minimization, define feasible(x) so there is a first feasible value x*:

x < x*  => feasible(x) is false
x >= x* => feasible(x) is true

Then the optimum is exactly the first true position. For maximization, a common shape is the reverse: candidates up to x* are feasible and larger candidates are not, so the task is to find the last true position.

The predicate does not need to return a solution witness on every probe. It only needs a correct decision. That separation can simplify hard-looking objectives. “What is the minimum largest partition sum?” becomes “Can the sequence be divided into at most k parts if each part may sum to at most x?” The latter can often be checked greedily in one pass.

There are three obligations:

1. Domain: every possible optimum lies in a totally ordered set the search can bracket.
2. Predicate: feasible(candidate) is correct for one candidate.
3. Monotonicity: once the predicate changes truth value, it never changes back.

Big-O analysis comes afterward. If the answer range contains R integer candidates and one feasibility check costs T, binary search costs $O(T log R)$. The logarithm is over the value range, not the input length. A range from 0 to $10^{18}$ still needs only about 60 halving steps, while an expensive predicate may dominate each step.

Prove Monotonicity Instead of Assuming It #

Monotonicity should follow from the problem constraints, not from a few observed outputs. For minimum processing capacity, if capacity c completes all work by the deadline, any larger capacity can imitate that schedule or finish sooner. Therefore feasibility cannot change from true back to false as capacity increases.

A proof often uses set containment. Let S(x) be the set of schedules allowed at candidate x. If x <= y implies S(x) is a subset of S(y), then a feasible schedule at x remains available at y. This establishes the false-to-true shape for minimization.

Predicates become non-monotone when candidate changes have competing effects. A compression level might reduce network time but increase CPU time, producing feasible, infeasible, then feasible regions. A price may increase revenue per unit while reducing demand irregularly. Binary search cannot select a global optimum from such a landscape without another structural argument.

Implementation details can also break mathematical monotonicity. Integer overflow may make a larger capacity produce a negative intermediate sum. A randomized heuristic may return false for a candidate that is actually feasible. A timeout inside the predicate may classify slow evaluation as infeasibility. From the search’s perspective, these are not incidental errors; they corrupt the ordered truth sequence on which correctness rests.

When the proof is difficult, write the predicate specification separately:

feasible(x) returns true if and only if there exists a valid construction whose objective value is at most x.

The “if and only if” matters. A checker that proves feasibility when it returns true but can return false for feasible candidates is a one-sided heuristic, not a safe boundary predicate. It may cause the search to skip the real optimum.

Choose an Integer Invariant and Keep It Visible #

Several correct binary-search templates exist, but mixing their boundary meanings creates off-by-one bugs. For the first true value in a closed interval [low, high], one useful invariant is:

The first feasible candidate is always inside [low, high].

This requires high to be known feasible. At each step, test the lower midpoint. If it is feasible, retain it by setting high = mid; otherwise exclude it and everything below it with low = mid + 1. Termination occurs when both boundaries identify one value.

function firstFeasible(
  low: bigint,
  high: bigint,
  feasible: (candidate: bigint) => boolean,
): bigint {
  if (low > high) throw new RangeError('search interval is empty');
  if (!feasible(high)) throw new RangeError('high must be feasible');

  while (low < high) {
    const middle = low + (high - low) / 2n;
    if (feasible(middle)) high = middle;
    else low = middle + 1n;
  }
  return low;
}

Another template uses sentinels with invariant feasible(low) === false and feasible(high) === true, while the answer lies in (low, high]. It stops when the boundaries are adjacent. This form is elegant when false and true sentinels are easy to provide, but the sentinels may sit outside the legal candidate domain. The predicate must not be called on an invalid sentinel.

For last true, reverse the updates and use an upper midpoint so a two-element interval makes progress:

middle = low + floor((high - low + 1) / 2)
true  => low = middle
false => high = middle - 1

Using the lower midpoint with low = middle can loop forever when high = low + 1. The safest review technique is not memorizing which +1 goes where. State the invariant, inspect the two-candidate case, and prove that every branch removes at least one candidate without removing the answer.

Work a Minimum-Capacity Example #

A batch worker must process five indivisible files with work sizes [30, 11, 23, 4, 20]. It has 10 hourly slots. In one slot it processes work from only one file at integer capacity c; an unfinished file continues in another slot. What is the smallest capacity that finishes all files?

For one file with work w, the required slots are ceil(w / c). The predicate is:

Capacity 0 is invalid. Capacity 30 is feasible because every file takes at most one slot, for five slots total. A useful lower bound is ceil(totalWork / 10) = ceil(88 / 10) = 9, although indivisibility may make that bound infeasible. The initial interval is therefore [9, 30] with a known-feasible upper endpoint.

Use integer ceiling division ceil(w / c) = floor((w + c - 1) / c) only when the addition cannot overflow. The equivalent floor((w - 1) / c) + 1 is safe for positive w, or quotient and remainder can be used directly. The predicate can stop as soon as required slots exceed the deadline.

function minimumCapacity(work: readonly bigint[], availableSlots: bigint): bigint {
  if (work.length === 0) return 0n;
  if (availableSlots <= 0n || work.some((amount) => amount <= 0n)) {
    throw new RangeError('work and available slots must be positive');
  }
  if (availableSlots < BigInt(work.length)) {
    throw new RangeError('each file requires at least one slot');
  }

  const total = work.reduce((sum, amount) => sum + amount, 0n);
  let low = (total + availableSlots - 1n) / availableSlots;
  let high = work.reduce((maximum, amount) => amount > maximum ? amount : maximum);

  const feasible = (capacity: bigint): boolean => {
    let used = 0n;
    for (const amount of work) {
      used += (amount - 1n) / capacity + 1n;
      if (used > availableSlots) return false;
    }
    return true;
  };

  while (low < high) {
    const middle = low + (high - low) / 2n;
    if (feasible(middle)) high = middle;
    else low = middle + 1n;
  }
  return low;
}

Trace the probes:

The answer is 11. Verification has two sides: capacity 11 is feasible, and its predecessor 10 is infeasible. For a first-true search, those boundary checks are a compact certificate of optimality once monotonicity is established.

Derive Bounds That Are Correct Before They Are Tight #

A bound is part of the proof. An overly broad valid interval costs extra logarithmic iterations; an invalid tight interval can exclude the answer. Start with bounds that are obvious, then tighten them only with justified constraints.

For the capacity example, high = max(work) is feasible only because the number of available slots is at least the number of files. If there were fewer than five slots, no capacity could help under the rule that one slot serves only one file. The implementation should detect that impossible instance rather than claiming max(work) is feasible.

When no natural upper bound is known, exponential search can discover one. Begin with a legal positive candidate and repeatedly double it until feasible, checking for numeric overflow and a domain maximum. This adds logarithmic predicate calls and preserves correctness if a feasible value is guaranteed to exist within the representable domain.

Midpoint arithmetic deserves care in fixed-width languages. (low + high) / 2 can overflow even when both endpoints are valid. Use low + (high - low) / 2 when subtraction is safe, or unsigned/expanded arithmetic appropriate to the language. JavaScript number represents integers exactly only through Number.MAX_SAFE_INTEGER; use bigint when the answer or intermediate sums can exceed that range.

Predicate arithmetic needs the same scrutiny. Summing required capacity, distances, or costs may overflow before comparison with a limit. Often the predicate can saturate: once a sum exceeds the threshold, return false without computing the exact larger value. Saturating early both avoids overflow and saves work.

Empty inputs, impossible constraints, and answers at domain extremes need explicit API semantics. Returning a numeric sentinel such as -1 is common but can collide with a legal domain. A result union, exception, or optional value makes impossibility distinct from an optimum.

Treat Floating-Point Search as Approximation #

For a continuous answer, there may be no representable “first true” number. A real-valued boundary can lie between adjacent floating-point values, and rounding inside the predicate can create a narrow uncertain region. The search must define an approximation contract.

One approach runs a fixed number of iterations. Starting from a finite bracket [low, high], each iteration halves its width. After k iterations, the mathematical interval width is (high - low) / 2^k, until floating-point granularity prevents further movement. Fixed iterations give predictable cost and avoid a termination test that stalls due to scale.

An epsilon-based loop stops when the interval is sufficiently narrow:

function firstFeasibleApprox(
  low: number,
  high: number,
  feasible: (candidate: number) => boolean,
  absoluteTolerance: number,
  relativeTolerance: number,
): number {
  for (let iteration = 0; iteration < 200; iteration += 1) {
    const width = high - low;
    const scale = Math.max(1, Math.abs(low), Math.abs(high));
    if (width <= Math.max(absoluteTolerance, relativeTolerance * scale)) break;
    const middle = low + width / 2;
    if (middle === low || middle === high) break;
    if (feasible(middle)) high = middle;
    else low = middle;
  }
  return high;
}

Absolute tolerance controls error near zero; relative tolerance scales for large magnitudes. The return of high preserves the interpretation that the result is the feasible side of the bracket, assuming high began feasible and the predicate is numerically reliable. Returning the midpoint may be closer to the mathematical boundary but may be infeasible.

Do not use floating search when the domain is actually discrete money, bytes, timestamps, or fixed decimal units. Convert to cents, ticks, or scaled integers and recover exact boundary semantics. For numerical predicates, document tolerance and verify nearby values rather than asserting exact equality.

Recognize Predicates That Make Search Misleading #

A binary search can be asymptotically elegant while operationally wasteful. If each predicate rebuilds a large index or runs an expensive simulation from scratch, reducing probe count may not compensate for repeated setup. Factor candidate-independent preprocessing out of the predicate, reuse immutable data, and include predicate cost in complexity analysis.

Side effects are dangerous. A predicate that consumes an iterator, mutates shared state, or reserves capacity can return different answers for the same candidate. Make it pure where possible. If simulation requires mutable scratch memory, reset or recreate it deterministically for every call.

Caching predicate results rarely changes the number of probes because ordinary binary search does not repeat candidates, but caching subcomputations may help. Parallel evaluation of several candidates usually wastes work and complicates ordering; one correct answer narrows the interval enough to make other speculative probes irrelevant.

Common logical failures include:

• Searching for first true with an upper bound that has never been proven true.
• Using while (low <= high) with update rules from a while (low < high) template.
• Returning the last midpoint rather than the boundary variable whose invariant was proved.
• Reversing monotonic direction for a maximization problem.
• Treating approximate or timeout-limited feasibility as exact.
• Forgetting that a greedy checker itself needs a correctness proof.
• Allowing overflow, NaN, or rounding to make truth values change direction.

When the predicate is not monotone, alternatives include dynamic programming, convex optimization, ternary search under a proven unimodal objective, or direct enumeration over a small candidate set. Binary search is not a generic incantation for “find the best number.”

Verify the Boundary, Predicate, and Invariant #

Tests should target the transition rather than only ordinary middle cases. For a first-true integer search, include an answer at the lower bound, an answer at the upper bound, a two-candidate interval, one candidate, no feasible candidate, and values near the numeric limit. Instrument the predicate in a test to assert that every candidate is legal and the loop terminates within the expected logarithmic number of calls.

For small random instances, compute the optimum by brute-force enumeration and compare it with binary search. In the capacity example, generate a few positive work amounts and a slot limit, enumerate capacities from 1 through max(work), and select the first feasible value. This validates both the search and the checker against a simple oracle.

Test monotonicity directly on generated small domains: evaluate every candidate in order and fail if a true is followed by false for a first-true predicate. This does not replace a proof for unbounded production inputs, but it catches arithmetic, state-reset, and rounding bugs in the implementation.

Every returned integer result should satisfy boundary properties:

feasible(answer) is true
answer is the domain minimum, or feasible(answer - 1) is false

For last true, reverse them. For floating results, assert bracket width and the documented feasible-side property, then test across several scales. Include values where midpoint rounds to an endpoint.

In production, observe predicate-call count and time separately from total operation time. A sudden increase may mean bounds expanded, while slower predicates may indicate input growth. Log sanitized bounds and the returned answer for diagnostics, but avoid high-cardinality input payloads. If feasibility depends on mutable external state, snapshot that state or attach a version so all probes answer the same optimization question.

Binary search on the answer succeeds when optimization has one ordered transition. The algorithm is the small part: define a decision predicate, prove its direction, establish a valid bracket, and maintain a boundary invariant until one candidate remains. Integer arithmetic gives exact predecessor checks; floating point requires an approximation contract. With those obligations explicit, binary search becomes a dependable way to convert easy feasibility checks into globally optimal answers rather than a fragile collection of midpoint formulas.