binary-search

Halve a sorted interval on every comparison.

best: O(1)
average: O(log n)
worst: O(log n)
space: O(1)

reference implementation

verified source·read-only

loading editor

brief

Binary search keeps an interval [lo, hi] that is guaranteed to contain the target if it exists, probes the middle, and discards the half that cannot contain it. One comparison therefore eliminates half the search space instead of a single element.

the math

The invariant

If the target exists, it lies inside $[lo, hi]$ .
Every step either finds the target or shrinks the interval while preserving the invariant.

The probe

$mid = \lfloor (lo + hi) / 2 \rfloor$ splits the interval into two halves.
One comparison decides which half can still contain the target — half the candidates are eliminated.

Why O(log n)

After $k$ probes the interval length is at most $n / 2^k$ .
The search ends when the interval is empty, so $k \le \lfloor \log_2 n \rfloor + 1$ .
For $n = 1{,}000{,}000$ that is at most 20 probes.

Sortedness is required

The discard argument relies on every value left of $mid$ being $\le a[mid]$ and every value right of it being $\ge a[mid]$ .
Without sorted input, discarding a half is unsound.

Failure case

When $lo > hi$ the interval is empty: the target is absent.
The algorithm then returns $-1$ ; it never scans the whole array.

▍ Binary Search · random

requesting trace

· decoding trace

· replaying events

· mounting renderer

0/0

fun facts

John Mauchly described binary search in 1946, but the first correct published implementation did not appear until 1962.
Jon Bentley's 1986 Programming Pearls column reported that roughly 90% of professional programmers could not write it correctly from scratch.
In 2006 Joshua Bloch found the overflow bug in Java's Arrays.binarySearch: (low + high) / 2 overflows for large arrays; the fix is low + (high − low) / 2.
On a million-element array it needs at most 20 probes, while a linear scan could need a million — twenty halvings separate the two.

binary-searchstep 0/00%spaceplay←→steppprojectorrreset