210: Binary Search and Monotonic Search Spaces

Learning outcomes

By the end of this lesson, you can:

explain and apply exact search in a realistic implementation;
explain and apply lower and upper bounds in a realistic implementation;
explain and apply monotonic predicates in a realistic implementation;
explain and apply integer overflow in a realistic implementation;
explain and apply termination invariants in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you begin, retrieve one concrete example from an earlier project where you had to narrow a set of possibilities, find an insertion position, or decide whether a value was feasible. It does not have to have been called binary search. The point is to connect the vocabulary to a decision you have already made in code.

The lesson covers both an interview-sized algorithm and the reasoning that keeps a similar implementation safe in production. You should not be trying to memorize a loop template. Given a requirement, you should be able to identify the search space, state the invariant, choose its boundary convention, and explain what happens for invalid or extreme input.

Terminology

Exact search: Compare a target with a midpoint in a sorted range and discard the half that cannot contain the target. The result is usually an index, or a sentinel such as -1 when the target is absent.
Lower and upper bounds: A lower bound finds the first index whose value is not less than a target (>= target); an upper bound finds the first index whose value is greater than the target (> target). They are boundary operations, so they are especially useful with duplicates and insertion points.
Monotonic predicates: If can(x) changes from false to true, or from true to false, at most once as x increases, binary search can find the smallest or largest feasible x even when there is no array to inspect.
Integer overflow: In a fixed-width language, calculate a midpoint as lo + (hi-lo)/2 rather than (lo + hi)/2, because adding two large endpoints can overflow before the division. JavaScript numbers avoid typical integer overflow at ordinary array indices, but its safe-integer limits still matter for very large numeric domains.
Termination invariants: State which interval can still contain the answer and prove that every iteration shrinks that interval. A loop that happens to work on ordinary input is not enough; the invariant explains why it terminates and why the returned boundary is correct.
Binary search on real values: Approximate numeric search needs a precision or iteration bound and an error tolerance. It is an approximation, not an exact result, and its stopping rule must come from the numeric requirement.

Mental model

Treat Binary Search and Monotonic Search Spaces as a design problem with observable inputs, outputs, invariants, and failure modes. Binary search is not merely “find an element in a sorted array.” Its more general job is to locate a boundary in an ordered space where a predicate changes truth value. That space might be array indices, capacities, times, rates, or another ordered set of candidate answers.

For an exact search, the predicate is often “the value at this index is less than, equal to, or greater than the target.” For an answer-space problem, it might be “can this capacity ship every package within D days?” The array version and the answer-space version use the same underlying idea: once one side of the boundary has been ruled out, it stays ruled out.

A strong implementation makes its assumptions visible. It says whether the endpoints are inclusive, what the return value means when no answer exists, what ordering or monotonicity is required, and how invalid input is handled. It also narrows uncertainty at a measurable rate and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe.

A useful sequence for both interviews and production work is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a familiar loop. First state what must remain true. Then choose the mechanism that enforces it. If the input is not sorted, or if the predicate is not monotonic, binary search is not a clever shortcut; it is the wrong algorithm.

Deep dive

1. Exact search

The simplest binary-search problem is to determine whether a target occurs in a sorted collection. Compare the target with the midpoint. If the midpoint is too small, every item at or before it is too small; if it is too large, every item at or after it is too large. Only the remaining half needs to be searched.

Define the interval convention before writing the loop. With an inclusive interval, both lo and hi may still contain the answer, so the usual loop condition is lo <= hi and the discarded side must move past mid. With a half-open interval, [lo, hi), hi is an exclusive boundary, the loop is commonly lo < hi, and the update rules must preserve that meaning. Mixing those two conventions is a reliable way to create an off-by-one error or an infinite loop.

The cost is O(log n) comparisons for a sorted collection of length n, with O(1) auxiliary space for an iterative implementation. Sorting is not free: if the data is not already sorted, sorting it usually costs O(n log n) time and may dominate the search. A linear scan can therefore be the better choice for a small, one-off input, or whenever sorting would destroy the useful relationship between records and their original positions.

Decision rule: Use exact search deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Confirm that the ordering is real, stable enough for the operation, and not merely an accidental property of one sample.

2. Lower and upper bounds

Many real questions are not “is this value present?” They are “where would this value go?” or “what range contains all equal values?” That is the job of boundary searches.

The lower bound returns the first index i for which nums[i] >= target. If every value is smaller, it returns nums.length, which is a valid insertion position but not a valid element index. The upper bound returns the first index i for which nums[i] > target. For a sorted array, the equal values occupy [lowerBound(target), upperBound(target)). This half-open range is convenient because its length is the count of occurrences.

For example, in [1, 2, 2, 2, 5], the lower bound of 2 is 1, the upper bound is 4, and the duplicate range is indices 1 through 3. For a target smaller than all values, the lower bound is 0; for a target greater than all values, it is length. Those boundary returns should be part of the contract, not surprising implementation details.

The boundary search itself is O(log n) time and O(1) auxiliary space. It is useful for insertion into a sorted collection, range counting, pagination over ordered keys, and locating the first record that satisfies a threshold.

Decision rule: Use lower and upper bounds deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. In particular, distinguish “first value not less than” from “first value greater than”; changing one comparison changes the boundary and changes duplicate behavior.

3. Monotonic predicates

Binary search does not require direct access to an array value. It requires an ordered search space and a predicate whose result changes in one direction at most once. A predicate such as can(capacity) may be false for every capacity below a threshold and true for every capacity at or above it. The smallest true value is then a boundary that binary search can locate.

The predicate must actually be monotonic over the chosen domain. If it is false, false, true, true, searching for the first true is well-defined. If it is false, true, false, discarding a half based on the midpoint can discard a later valid answer. Establish the property before optimizing; a fast search over a non-monotonic predicate is still incorrect.

There must also be a search range and a meaningful feasibility contract. If no candidate is feasible, decide whether to return a sentinel, throw, or report an error. If the predicate is expensive, the total cost is O(log R) predicate evaluations for a range containing R candidates, multiplied by the cost of one evaluation. That multiplication matters in production: the binary-search loop may be logarithmic while the predicate scans a large dataset on every iteration.

Decision rule: Use monotonic predicates deliberately when they make the contract or invariant easier to prove. If they only reduce typing while hiding an assumption, prefer the more explicit design. Write down what “false” and “true” mean at the endpoints before choosing whether you want the first feasible or last feasible candidate.

4. Integer overflow

The midpoint formula looks harmless, but in a fixed-width integer language (lo + hi) / 2 can overflow even when the midpoint itself would fit. The addition happens first. Use lo + (hi-lo)/2; the difference is bounded by the current search interval, so the intermediate addition is safer under the usual non-negative index constraints. In integer code, use integer division or an equivalent floor operation as required by the language.

JavaScript's number type represents ordinary array indices without the classic 32-bit overflow problem, and Math.floor((hi - lo) / 2) gives an integer midpoint for this example. That does not mean every numeric search is safe. JavaScript numbers lose integer precision beyond Number.MAX_SAFE_INTEGER, and an unsafe value can make comparisons or updates unreliable. For huge discrete domains, use bigint where appropriate, or constrain and validate the domain so all arithmetic stays within safe-integer bounds. Do not mix number and bigint arithmetic without an explicit conversion strategy.

Decision rule: Treat overflow prevention as part of the numeric contract, not as an optional micro-optimization. Use a midpoint calculation appropriate to the language and type, state the permitted range, and test values near that range. If the domain is real-valued, overflow is not the only concern; precision and termination criteria become central as well.

5. Termination invariants

The most important question in a binary-search loop is: what does the current interval mean? For a lower bound over [lo, hi), the answer is still somewhere in that interval, while every index below lo is known to contain a value smaller than the target. Every iteration chooses mid inside the interval. If nums[mid] < target, mid cannot be the answer, so the next interval starts at mid + 1; otherwise mid may still be the answer, so the next interval ends at mid.

The interval becomes smaller on every iteration. When lo === hi, no candidates remain between the endpoints, and lo is the first position that was not ruled out. This is both the termination proof and the correctness argument. The comparison is only one part of the implementation; the updates and the meaning of the returned endpoint complete the proof.

For exact search with an inclusive interval, a successful comparison returns immediately. When the midpoint is too small or too large, move beyond it so the interval strictly shrinks. For either convention, test arrays of length 0, 1, and 2, as well as targets below, inside, and above the range. These cases expose most boundary mistakes quickly.

Decision rule: Use termination invariants deliberately when they make the contract or invariant easier to prove. If a loop cannot explain which values have been eliminated and why its interval shrinks, stop and revise the model before debugging syntax. Most binary-search defects are invariant or termination defects rather than comparison-operator typos.

6. Binary search on real values

The same boundary idea works over real numbers when a predicate is monotonic, but the result is approximate. Search between a lower and upper numeric bound, evaluate the midpoint, and retain the half that could contain a value within the required tolerance. Stop after a specified number of iterations or when hi - lo <= epsilon.

The stopping rule should match the requirement. An absolute tolerance may be appropriate for a measurement near zero; a relative tolerance may be more useful across values with very different scales. A fixed iteration count is often easier to reason about, while an epsilon-based loop must still account for floating-point precision and ensure that progress continues. Report the approximation and its error guarantee clearly rather than presenting it as an exact answer.

Decision rule: Use binary search on real values deliberately when it makes the numeric contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Document the initial range, monotonic predicate, stopping condition, and accepted error.

Worked example

Start with the requirement, not with a loop: “Return the first position at which target could be inserted into an ascending numeric array without violating the ordering.” That wording tells us this is a lower-bound problem, not merely an exact-presence search. The input is a read-only sorted array of numbers and a numeric target. The output is an integer in [0, nums.length]; returning nums.length is correct when the target belongs after every element. A caller that needs to know whether the target exists must compare the returned position with nums.length and then inspect that position.

Here is an implementation using the half-open interval [lo, hi). Initially every insertion position from 0 through nums.length is possible, represented by lo = 0 and hi = nums.length. The loop keeps the answer in that interval. When the midpoint value is less than the target, that midpoint and everything before it are too small, so lo advances to mid + 1. Otherwise the midpoint remains a possible answer, so hi moves to mid.

function lowerBound(nums: readonly number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

The non-null assertion is safe only because mid < hi and hi <= nums.length imply mid < nums.length whenever the loop runs. TypeScript does not infer that array-index fact from the loop invariant, so the assertion documents an assumption the algorithm has already proved. It is not validation of an unsorted or malformed array.

Walk the implementation through at least four cases. On [1, 3, 5, 7] with target 5, the search narrows to index 2. With target 4, it returns 2, the position before 5. On an empty array it returns 0, the only valid insertion position. With duplicates such as [1, 2, 2, 4] and target 2, it returns 1, the first equal value rather than an arbitrary matching index. A target larger than every element returns nums.length.

For each case, state what the caller observes and which layer owns the concern. The algorithm owns ordering and boundary semantics. Input validation belongs at the boundary if the application accepts untrusted or dynamically shaped data; for example, that layer can reject a non-array value or non-finite number. A repository or service that supplies the array owns the contract that it is sorted. A duplicate request or retry should not be confused with a new search result; if the surrounding operation has side effects, idempotency belongs to that operation's contract. A concurrent update matters if the collection can change during the search: searching a stable in-memory snapshot is different from searching a mutable data source. A dependency failure while obtaining the data is not a binary-search result and should remain an explicit dependency error rather than being disguised as “not found.”

The lower-bound loop performs O(log n) iterations and uses O(1) auxiliary space. The predicate here is one array comparison, so the total running time is O(log n). If a monotonic answer-space predicate scans all packages on every call, the outer search is still logarithmic in the answer range, but the full cost is O(log R * cost(can)); that is the figure to use when evaluating the production design.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. A binary search over a sorted snapshot is deterministic; a binary search over a collection being mutated underneath it may not be. Make the snapshot, ordering, and freshness assumptions explicit.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. An O(log n) search is not automatically the right choice if constructing or sorting the data costs more than a simple scan, or if every predicate evaluation triggers expensive I/O.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Binary search does not validate authorization, sanitize input, or make stale data current.

Guided lab

Implement exact search, lower and upper bounds, search in a rotated sorted array, and “minimum capacity to ship within D days” as binary search on an answer. For the shipping problem, write the monotonic predicate explicitly: for a proposed capacity, simulate the loading process and return whether all packages can be shipped within D days. Capacities below the minimum feasible capacity must be false, and that capacity and every larger capacity must be true. The search should then return the smallest true capacity.

For the rotated-array problem, state the extra assumption your approach needs. In the common distinct-values version, at least one side of the midpoint is sorted; use that fact to decide which half can contain the target. If duplicates are allowed, explain how equal endpoints can make that decision ambiguous and what additional step or complexity trade-off follows. Do not silently apply a distinct-values proof to duplicate data.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For verification, include empty input where the contract permits it, a one-element input, an absent target, duplicates, targets at both extremes, and the smallest valid value of D. For answer-space search, test an impossible contract if one is allowed, a capacity equal to the largest single package, and a capacity equal to the total weight. Also inspect that the predicate is not mutating shared input and that every iteration advances or narrows the interval.

Edge cases and failure modes

Exact search: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. An unsorted input invalidates the discard-half argument; it is not merely an unusual result.
Lower and upper bounds: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include targets before the first item and after the last item, and verify whether the returned endpoint is an insertion position or an element index.
Monotonic predicates: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check the predicate at both endpoints and verify that it does not change direction more than once.
Integer overflow: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. In fixed-width languages, exercise endpoint values near the type limit; in JavaScript, test safe-integer boundaries and avoid assuming arbitrary integer precision.
Termination invariants: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Log or inspect lo, mid, and hi for a failing case and confirm that the interval strictly shrinks.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. First decide whether the task asks for an exact match, a first/last boundary, or a feasible answer.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. A non-null assertion can silence TypeScript without proving that the input is sorted or that the index is valid.
Testing only the happy path and therefore discovering contracts only after integration. Empty arrays, duplicates, endpoints, and impossible predicates should be deliberate tests.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Include sorting, predicate cost, data acquisition, and memory behavior in the comparison.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. A client can alter its target, capacity, or displayed result; server-side code must enforce the relevant contract.
Mixing inclusive and half-open interval conventions. This commonly causes mid to be reconsidered forever or causes a valid endpoint to be skipped.
Returning a matching index when the caller needs a boundary. An exact search can find one duplicate, while a lower or upper bound defines the whole duplicate range.

For debugging, reproduce the smallest failing case, inspect the actual values and the search bounds, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. If the result is wrong, check sortedness or monotonicity before changing the comparison. If the loop hangs, record successive lo, mid, and hi values and look for an update that leaves the interval unchanged. If a production result changes between runs, investigate snapshot consistency, concurrent mutation, stale data, and nondeterministic predicate behavior.

Interview questions

What problem does Exact search solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Lower and upper bounds solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Monotonic predicates solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Integer overflow solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Termination invariants solve, and what trade-off or failure mode would make you choose a different approach?

In a strong answer, name the precondition, define the interval or boundary semantics, give the time and space complexity, and mention at least one edge case. Be prepared to explain why a predicate remains monotonic and how you would respond if the data were unsorted, mutable, duplicated, or too large for the numeric type.

Checkpoint

Without notes, explain Binary Search and Monotonic Search Spaces to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. As a self-check, explain what each returned boundary means, why the loop terminates, and what the algorithm costs when the input is already sorted versus when sorting or predicate evaluation is included.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.