Home/Searching/Binary search
Search algorithmsCTRL K

Binary search

· sorted array · halve the range
/searching/binary-search
COMPARISONS
0
at most ⌈log₂ n⌉ + 1
RANGE
32/ 32
elements still possible
MIDDLE
—
index being probed
TARGET
33
value we look for
RESULT
—
index once found
discardedmiddletargetfound
n = 32 · target 33 · seed 7 · 10 steps
step 0 / 9
Size32
binary_search.ts
1
function binarySearch(array: number[], target: number) {
2
  let low = 0, high = array.length - 1;
3
  while (low <= high) {
4
    const middle = (low + high) >> 1;
5
    if (array[middle] === target) return middle;
6
    if (array[middle] < target) low = middle + 1;
7
    else high = middle - 1;
8
  }
9
  return -1;
10
}
CURRENT STEP
line 2

Look for 33. The whole range [0, 31] is possible.

// how it works

Understanding Binary search

binary search · twenty questions on a sorted array
01

The idea

Binary search keeps a range [low, high] that must contain the target, looks at the middle element, and throws away the half that cannot contain it. Because the array is sorted, one comparison tells which half: smaller means look left, larger means look right.

Each probe halves the range, so a million elements take at most twenty probes. The precondition is the whole trick: sorting once costs n log n, and after that every lookup is logarithmic.

02

The four stages

1
probemiddle ← (low + high) / 2
2
comparearray[middle] against the target
3
halvekeep the half that can hold it
4
foundarray[middle] = target, or range empty
03

Complexity

best
O(1)target sits exactly in the middle
average
O(log n)≈ log₂ n − 1 probes
worst
O(log n)⌈log₂ n⌉ + 1 probes, present or not
space
O(1)two indices
04

Versus its siblings

COMPARISONS AT N = 1 000 · TARGET PRESENT
linear
500
jump
63
binary
10
interpolation
4
hash table
1
average over random targets · sorted input for all but linear
05

Pseudocode

BINARYSEARCH(array, target)
  low ← 0; high ← n − 1
  while low ≤ high
    middle ← ⌊(low + high) / 2⌋
    if array[middle] = target: return middle
    if array[middle] < target: low ← middle + 1 else high ← middle − 1
  return −1
06

When to use

Any sorted array, or anything that behaves like one: a monotone function, a version history, a range of answers to a yes/no question.
Lookups that repeat: pay the sort once, then answer each query in twenty steps.
07

Pitfalls

(lo + hi) / 2 overflows in fixed-width integers; write lo + (hi − lo) / 2. Java's own binary search had this bug for nine years.
Off-by-one errors in the bounds: an inclusive hi needs lo ≤ hi and hi = mid − 1; mixing conventions loops forever.
On a linked list there is no O(1) access to the middle: the halving buys nothing.
08

History

John Mauchly presented binary search in 1946, in the same Moore School lectures that described insertion sort. The first version that worked for every array size was not published until 1962, by Lehmer and then Bottenbruch, and Jon Bentley found in 1986 that 90% of professional programmers could not write it correctly.

Back to Searching