Binary Search

in reviewThis lesson is complete and being validated before release - details may still change.

Binary search

Loading interactive demo…

The top row is the sorted array, every value shown. Each read adds a row beneath it: the cells the target could still be in, the one cell that was read, and the half that read ruled out. The strips beneath hold the values in the array and a few it does not hold; tap any of them to search for it.Take the tour, or press and explore. Legend:

The panel beside the stage is the real BinarySearch class from the published library executing in your browser, with the current line highlighted.

The cell read this step: the middle of the range, or the next cell of a scan.
Cells still in play when the row was read, with their values.
The half the read ruled out, gone for good.
The target, found: ringed in its row and in the array.
The slot a missing target would take to keep the order.
The faint finished search, before play reaches it.

reads counts the cells read so far; range is how many cells could still hold the target; bound is the most reads binary search can need on an array this size; a scan is what reading from the left would cost for this target.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A sorted array knows more than it shows. Ask an unsorted array whether it holds 24 and the only honest method is to read every cell: a value you have not read tells you nothing about one you have. Sort the array and every read says something about every cell. If the middle holds 37 and you want 24, then every cell after the middle holds something bigger than 37, so none of them can be 24. One read has ruled out half the array.

The invariant. Binary search keeps two indices, $lo$ and $hi$ , with one promise: if the target is in the array at all, it lies in $values[lo..hi]$ . Before the first read the promise is trivially kept, since the range is the whole array. Each read of the middle either finds the target or shrinks the range to the half that can still keep the promise: a middle too big makes $hi = mid - 1$ , a middle too small makes $lo = mid + 1$ . When $hi$ passes $lo$ the range is empty, and the promise says the target cannot be anywhere.

Halving to the bound. A range of $n$ cells becomes at most $\lfloor n / 2 \rfloor$ cells after a read, since the middle is gone with everything on one side of it. After $k$ reads at most $n / 2^k$ cells remain, so the range is empty once $2^k > n$ :

\text{reads} \le \lceil \log_2 (n + 1) \rceil

which is what the bound readout shows. Sixteen cells need at most five reads, a thousand need ten, a million need twenty, and a billion need thirty. A scan needs up to $n$ . That gap, $O(\log n)$ against $O(n)$ , is why so much of computing is spent keeping things sorted: the sort is paid once, and every question afterward is cheap.

What a miss tells you. When the range empties, $lo$ is sitting on the first cell whose value exceeds the target, and $hi$ on the last whose value is smaller. So $lo$ is exactly the slot the target would take to keep the array sorted, the slot mark on the stage. Return it instead of a plain "not found" and the loop becomes a lower bound: the same shape finds the first value at least as large as any key, and it is what standard libraries ship as bisect_left and lower_bound.

The bug in the middle. The obvious midpoint is $(lo + hi) / 2$ , and in a language with fixed-width integers it is wrong: for arrays of about a billion elements the sum overflows, goes negative, and the next read is off the front of the array. The Java library carried that line for about nine years. The fix the stage runs is $lo + \lfloor (hi - lo) / 2 \rfloor$ , which never adds two large numbers; (lo + hi) >>> 1 is the other common repair. The lesson Bentley drew from his own buggy version stands: write the invariant down and check every line against it.

Where this goes next. Binary search gets its speed from a shape, the sorted order, that it never has to maintain: the array is given sorted. Insert one new value and keeping that order costs a shift of up to $n$ cells. The next lesson builds a structure that keeps just enough order to answer one question, the smallest value, in $O(1)$ while still taking inserts in $O(\log n)$ : the heap.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The invariant is a comment, then a loop condition. The while (lo <= hi) test is the whole termination argument: the range is non-empty exactly while the promise can still be kept, and an empty range is a proof of absence rather than a failure.
lo + ((hi - lo) >> 1) is the overflow-safe midpoint. JavaScript numbers would not overflow at these sizes, but the published form is the one that stays correct in every language the lesson's readers will write it in.
range is emitted before the read. Each iteration first states what the range is, then reads its middle, then names the half kept, so one row of the stage is one iteration and the trace reads as the invariant, the evidence, and the inference.
finish emits found and missing once each. Both the halving loop and the linear scan end through the same method, so the verdict's trace tag has a single call site in the file and the stage can map it to one line.
The scan stops early. A scan over a sorted array can stop at the first value past the target, which is kinder to it than the usual "read everything" version; even so it costs up to $n$ reads, and scanCost reports exactly how many for the chosen target.
insertAt is lo. The missing verdict carries the slot the target would take, which is lo when the range closes, so the same class serves as a lower-bound search for free.

Binary search is older than the stored-program computer. John Mauchly described it in 1946 in the Moore School Lectures, the first course on computing ever given. The idea looked finished and was not: for fourteen years every published version only worked on arrays whose length was one less than a power of two, and Derrick Henry Lehmer's 1960 algorithm was the first to handle any length. The details kept biting: Hermann Bottenbruch's 1962 ALGOL 60 version moved the equality test to the end, and in 2006 Joshua Bloch showed that the midpoint line most textbooks teach overflows on large arrays.

1946John Mauchly - Makes the first mention of binary search in the Moore School Lectures at the University of Pennsylvania, the first course ever given on computing.source
1960Derrick Henry Lehmer - Publishes the first binary search that works on arrays of every length; the versions before it only handled lengths one less than a power of two.source
1962Hermann Bottenbruch - Gives an ALGOL 60 implementation that moves the equality check to the end of the loop, one comparison per iteration at the cost of about one more iteration.source
2006Joshua Bloch - Shows that the midpoint line mid = (low + high) / 2 overflows for arrays of a billion or more elements, a bug that sat in the Java library's binary search for about nine years.source

Used today

Standard libraries - Python's bisect module, C++'s lower_bound, and Java's Arrays.binarySearch are this loop; the lower-bound form returns the insertion slot the missing case reports here.
git bisect - Finding the commit that broke a build is a binary search over history: test the middle commit and discard the half that cannot contain the culprit.
Database indexes - Inside a B-tree page the keys are sorted, and finding the child to descend into is a binary search over that page.

n16 values

seed7

mode

reads: 4
range: 1 of 16
bound: 5 reads
a scan: 5 reads

binary-search.ts

import type { Tracer } from "../trace";/** How the search walks the array: every element from the left, or the middle of what remains. */export const SEARCH_MODES = ["linear", "binary"] as const;export type SearchMode = (typeof SEARCH_MODES)[number];/** Arrays longer than this are refused, so a traced run stays a stage's worth. */export const SEARCH_MAX_LENGTH = 64;/** Values live in [SEARCH_MIN_VALUE, SEARCH_MAX_VALUE], two digits at most, so a tile can show one. */export const SEARCH_MIN_VALUE = 1;export const SEARCH_MAX_VALUE = 99;export interface SearchOptions {  /** Default binary. */  mode?: SearchMode;}export interface SearchResult {  /** Where the target sits, or null when the array does not hold it. */  index: number | null;  /** Where the target belongs: its index when found, otherwise the index it would be inserted at to keep the order. */  insertAt: number;  /** Elements read. */  probes: number;}/** * Searching a sorted array. A linear scan reads from the left and stops * at the target or at the first value past it, so it costs up to n * reads. Binary search keeps a range [lo, hi] that must hold the * target if the array does, reads the middle element, and throws away * the half that cannot hold the target: a value smaller than the * target rules out everything at or before it, a larger one everything * at or after it. Each read halves the range, so n elements take at * most ceil(log2(n + 1)) reads, and an empty range proves the target * absent, with lo naming the slot it would occupy. * * Time: O(log n) reads for binary search, O(n) for the scan. Space: * O(1) beyond the array. */export class BinarySearch {  readonly mode: SearchMode;  constructor(options: SearchOptions = {}, private readonly tracer?: Tracer) {    this.mode = options.mode ?? "binary";  }  /** Finds target in a strictly increasing array of integers, or where it would go. */  search(values: readonly number[], target: number): SearchResult {    BinarySearch.check(values, target);    if (this.mode === "linear") return this.scan(values, target);    let lo = 0;    let lowestCandidate = 0;    let hi = values.length - 1;    let highestCandidate = values.length - 1;    let probes = 0;    while (lo <= hi) {    while (lowestCandidate <= highestCandidate) {      // Invariant: if the target is in the array, it is in values[lo..hi].      // ▸ the target, if it is here at all, sits somewhere in values[lo..hi]      this.tracer?.emit("range", { lo, hi, size: hi - lo + 1 });      this.tracer?.emit("range", { lowestCandidate, highestCandidate, size: highestCandidate - lowestCandidate + 1 });      const mid = lo + ((hi - lo) >> 1);      const middleIndex = lowestCandidate + ((highestCandidate - lowestCandidate) >> 1);      const value = values[mid]!;      const value = values[middleIndex]!;      probes++;      // ▸ read the middle element of the range; the overflow-safe midpoint      this.tracer?.emit("probe", { mid, value, target, probes });      this.tracer?.emit("probe", { middleIndex, value, target, probes });      if (value === target) return this.finish(mid, mid, probes);      if (value === target) return this.finish(middleIndex, middleIndex, probes);      if (target < value) {        hi = mid - 1;        highestCandidate = middleIndex - 1;        // ▸ the middle is too big, so is everything after it: keep the left half        this.tracer?.emit("left", { lo, hi });        this.tracer?.emit("left", { lowestCandidate, highestCandidate });      } else {        lo = mid + 1;        lowestCandidate = middleIndex + 1;        // ▸ the middle is too small, so is everything before it: keep the right half        this.tracer?.emit("right", { lo, hi });        this.tracer?.emit("right", { lowestCandidate, highestCandidate });      }    }    // The range closed without a match: lo is the first index whose value exceeds the target.    return this.finish(null, lo, probes);    return this.finish(null, lowestCandidate, probes);  }  /** Reads from the left; sorted input lets it stop at the first value past the target. */  private scan(values: readonly number[], target: number): SearchResult {    let probes = 0;    for (const [index, value] of values.entries()) {      probes++;      // ▸ a linear scan reads the next element; sorted input lets it stop at the first value past the target      this.tracer?.emit("scan", { index, value, probes });      if (value === target) return this.finish(index, index, probes);      if (value > target) return this.finish(null, index, probes);    }    return this.finish(null, values.length, probes);  }  /** The verdict: the target's index, or the slot it would take. */  private finish(index: number | null, insertAt: number, probes: number): SearchResult {    // ▸ the middle is the target    if (index !== null) this.tracer?.emit("found", { index, probes });    // ▸ the range closed without a match; lo is the slot the target would take    else this.tracer?.emit("missing", { probes, insertAt });    return { index, insertAt, probes };  }  /** Reads a scan would take: one per element up to and including the target or the first value past it. */  static scanCost(values: readonly number[], target: number): number {    const past = values.findIndex((value) => value >= target);    return past === -1 ? values.length : past + 1;  }  /** The most reads a binary search of n elements can take: ceil(log2(n + 1)). */  static bound(n: number): number {    let reads = 0;    let remaining = n;    while (remaining > 0) {      remaining = remaining >> 1;      reads++;    }    return reads;  }  private static check(values: readonly number[], target: number): void {    if (values.length > SEARCH_MAX_LENGTH) throw new RangeError(`${values.length} values exceeds ${SEARCH_MAX_LENGTH}`);    if (!Number.isInteger(target)) throw new RangeError("target must be an integer");    values.forEach((value, index) => {      if (!Number.isInteger(value) || value < SEARCH_MIN_VALUE || value > SEARCH_MAX_VALUE) {        throw new RangeError(`values must be integers in [${SEARCH_MIN_VALUE}, ${SEARCH_MAX_VALUE}]`);      }      if (index > 0 && value <= values[index - 1]!) throw new RangeError("values must be strictly increasing");    });  }}

target =: 24
probes =: 4
insertAt =: 4
n =: 16
bound =: 5
scanCost =: 5
index =: 4

binary search over 16 values took 4 reads to find 24 at index 4; binary search is bounded by 5 reads here, and a scan would take 5 reads.

import type { Tracer } from "../trace";/** How the search walks the array: every element from the left, or the middle of what remains. */export const SEARCH_MODES = ["linear", "binary"] as const;export type SearchMode = (typeof SEARCH_MODES)[number];/** Arrays longer than this are refused, so a traced run stays a stage's worth. */export const SEARCH_MAX_LENGTH = 64;/** Values live in [SEARCH_MIN_VALUE, SEARCH_MAX_VALUE], two digits at most, so a tile can show one. */export const SEARCH_MIN_VALUE = 1;export const SEARCH_MAX_VALUE = 99;export interface SearchOptions { /** Default binary. */ mode?: SearchMode;}export interface SearchResult { /** Where the target sits, or null when the array does not hold it. */ index: number | null; /** Where the target belongs: its index when found, otherwise the index it would be inserted at to keep the order. */ insertAt: number; /** Elements read. */ probes: number;}/** * Searching a sorted array. A linear scan reads from the left and stops * at the target or at the first value past it, so it costs up to n * reads. Binary search keeps a range [lo, hi] that must hold the * target if the array does, reads the middle element, and throws away * the half that cannot hold the target: a value smaller than the * target rules out everything at or before it, a larger one everything * at or after it. Each read halves the range, so n elements take at * most ceil(log2(n + 1)) reads, and an empty range proves the target * absent, with lo naming the slot it would occupy. * * Time: O(log n) reads for binary search, O(n) for the scan. Space: * O(1) beyond the array. */export class BinarySearch { readonly mode: SearchMode; constructor(options: SearchOptions = {}, private readonly tracer?: Tracer) { this.mode = options.mode ?? "binary"; } /** Finds target in a strictly increasing array of integers, or where it would go. */ search(values: readonly number[], target: number): SearchResult { BinarySearch.check(values, target); if (this.mode === "linear") return this.scan(values, target); let lo = 0; let lowestCandidate = 0; let hi = values.length - 1; let highestCandidate = values.length - 1; let probes = 0; while (lo <= hi) { while (lowestCandidate <= highestCandidate) { // Invariant: if the target is in the array, it is in values[lo..hi]. // ▸ the target, if it is here at all, sits somewhere in values[lo..hi] this.tracer?.emit("range", { lo, hi, size: hi - lo + 1 }); this.tracer?.emit("range", { lowestCandidate, highestCandidate, size: highestCandidate - lowestCandidate + 1 }); const mid = lo + ((hi - lo) >> 1); const middleIndex = lowestCandidate + ((highestCandidate - lowestCandidate) >> 1); const value = values[mid]!; const value = values[middleIndex]!; probes++; // ▸ read the middle element of the range; the overflow-safe midpoint this.tracer?.emit("probe", { mid, value, target, probes }); this.tracer?.emit("probe", { middleIndex, value, target, probes }); if (value === target) return this.finish(mid, mid, probes); if (value === target) return this.finish(middleIndex, middleIndex, probes); if (target < value) { hi = mid - 1; highestCandidate = middleIndex - 1; // ▸ the middle is too big, so is everything after it: keep the left half this.tracer?.emit("left", { lo, hi }); this.tracer?.emit("left", { lowestCandidate, highestCandidate }); } else { lo = mid + 1; lowestCandidate = middleIndex + 1; // ▸ the middle is too small, so is everything before it: keep the right half this.tracer?.emit("right", { lo, hi }); this.tracer?.emit("right", { lowestCandidate, highestCandidate }); } } // The range closed without a match: lo is the first index whose value exceeds the target. return this.finish(null, lo, probes); return this.finish(null, lowestCandidate, probes); } /** Reads from the left; sorted input lets it stop at the first value past the target. */ private scan(values: readonly number[], target: number): SearchResult { let probes = 0; for (const [index, value] of values.entries()) { probes++; // ▸ a linear scan reads the next element; sorted input lets it stop at the first value past the target this.tracer?.emit("scan", { index, value, probes }); if (value === target) return this.finish(index, index, probes); if (value > target) return this.finish(null, index, probes); } return this.finish(null, values.length, probes); } /** The verdict: the target's index, or the slot it would take. */ private finish(index: number | null, insertAt: number, probes: number): SearchResult { // ▸ the middle is the target if (index !== null) this.tracer?.emit("found", { index, probes }); // ▸ the range closed without a match; lo is the slot the target would take else this.tracer?.emit("missing", { probes, insertAt }); return { index, insertAt, probes }; } /** Reads a scan would take: one per element up to and including the target or the first value past it. */ static scanCost(values: readonly number[], target: number): number { const past = values.findIndex((value) => value >= target); return past === -1 ? values.length : past + 1; } /** The most reads a binary search of n elements can take: ceil(log2(n + 1)). */ static bound(n: number): number { let reads = 0; let remaining = n; while (remaining > 0) { remaining = remaining >> 1; reads++; } return reads; } private static check(values: readonly number[], target: number): void { if (values.length > SEARCH_MAX_LENGTH) throw new RangeError(`${values.length} values exceeds ${SEARCH_MAX_LENGTH}`); if (!Number.isInteger(target)) throw new RangeError("target must be an integer"); values.forEach((value, index) => { if (!Number.isInteger(value) || value < SEARCH_MIN_VALUE || value > SEARCH_MAX_VALUE) { throw new RangeError(`values must be integers in [${SEARCH_MIN_VALUE}, ${SEARCH_MAX_VALUE}]`); } if (index > 0 && value <= values[index - 1]!) throw new RangeError("values must be strictly increasing"); }); }}