Binary Search

Why This Matters

Binary search is the canonical O(log n) algorithm. A billion-element sorted array takes about 30 comparisons, not a billion.

It is also famously easy to implement incorrectly. Jon Bentley reported that many professional programmers introduced bugs when asked to write it from memory, and Joshua Bloch later described a midpoint overflow bug in common textbook and library implementations.

Learning Objectives

By the end, you should be able to:

State the sortedness or monotonicity condition that makes binary search valid.
Implement exact search and lower-bound search with a clear loop invariant.
Explain why halving gives O(log n) comparisons.
Avoid midpoint overflow and off-by-one interval bugs.
Transfer the idea to "binary search the answer" over monotone predicates.

Core Idea

Maintain a search interval that still could contain the target. Compare the target with the midpoint, then discard the half that cannot contain it.

Variant	Interval	Returns	Typical use
Exact search	closed `[lo, hi]`	index or not found	membership
Lower bound	half-open `[lo, hi)`	first index with `A[i] >= t`	insertion point
Upper bound	half-open `[lo, hi)`	first index with `A[i] > t`	count duplicates

The invariant is the whole algorithm: if the target exists, it remains inside the current interval.

Non-Example or Failure Mode

Binary search is invalid on an unsorted array or a non-monotone predicate. If the comparison does not tell you which half can be discarded, the algorithm can confidently throw away the answer.

The failure mode is false structure: code that halves an interval can look like binary search while violating the invariant that all discarded candidates are impossible.

Worked Example

Search for 14 in [2, 5, 8, 14, 19, 23, 31].

lo = 0, hi = 6
mid = 3, A[mid] = 14
return 3

Search for 15 in the same array.

lo = 0, hi = 6
mid = 3, A[mid] = 14, move lo to 4
mid = 5, A[mid] = 23, move hi to 4
mid = 4, A[mid] = 19, move hi to 3
lo > hi, not found

Each comparison removes about half of the remaining candidates.

Builder Connections

Sorted indexes use binary-search-style lookup.
Search over answer uses binary search on monotone predicates.
Lower-bound operations power insertion points, range counts, and time-series lookups.
Divide-and-conquer algorithms reuse the same halving intuition.
Production code should use standard library versions unless implementing the invariant is the exercise.

Common Mistakes

Mistake	Correction
Searching an unsorted array.	Binary search needs sorted values or a monotone predicate.
Mixing interval conventions.	Choose closed `[lo, hi]` or half-open `[lo, hi)` and make every update match it.
Writing `(lo + hi) / 2` in fixed-width languages.	Use `lo + floor((hi - lo) / 2)` to avoid overflow.
Using exact-search updates in lower-bound code.	Lower-bound usually keeps `mid` with `hi = mid` when `values[mid] >= target`.
Forgetting adjacent termination.	Ensure the interval shrinks on every iteration.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What sortedness assumption does binary search require?	Values must be sorted by the comparison used, or the predicate must be monotone.
Example / non-example	Can binary search find a target in an unsorted array?	Not reliably; the midpoint comparison gives no valid half to discard.
Computation	How many comparisons are needed for at most one billion items?	About `ceil(log2(1,000,000,000)) = 30`.
Proof	What loop invariant makes exact search correct?	If the target exists, it remains within the current search interval.
Transfer	How does lower-bound support inserting into a sorted array?	It returns the first index where the target can be inserted without breaking sorted order.

Exercises

Beginner:

Run exact binary search by hand for target 7 in [1, 3, 5, 7, 9].
Explain why the midpoint formula lo + floor((hi - lo) / 2) avoids overflow.
Identify whether a loop is using a closed or half-open interval.

Intermediate:

Implement lower-bound and test it on arrays with duplicates.
Use lower-bound and upper-bound to count occurrences of a value.

Challenge:

Binary search the answer for the smallest capacity that can ship packages within d days, given a monotone feasibility predicate.

Diagram Recommendation

Type: interval-halving trace.

Caption: "Each midpoint comparison discards one half while preserving the invariant."

Purpose: Make the loop invariant visible and separate exact search from lower-bound search.

Implementation Task

Implement lower-bound using a half-open interval.

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

Test it on empty arrays, one-element arrays, duplicate values, targets smaller than all values, and targets larger than all values.

Next Topics

References

Bentley, J. Programming Pearls (2nd ed., 2000). Ch. 4.
Bloch, J. (2006). "Extra, Extra: Nearly All Binary Searches and Mergesorts are Broken." Google Research Blog.
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Sec. 2.3.5.
Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed., 1998). Sec. 6.2.1.