AlgoViz
learn/Algorithms/Binary Search
ƒ(x) SearchingCore interactive

Binary Search

Halve the search space every step. O(log n).

binary_search
step 1 / 9
lo
4
0
7
1
9
2
21
3
24
4
29
5
39
6
42
7
43
8
52
9
59
10
78
11
hi
83
12

Search 83 in a sorted array.

active rangemideliminatedfound
speed1×
target = 83

How it works

Binary search exploits sorted order: compare the middle, then discard half the array each step. Twenty comparisons suffice to find any item among a million. The idea generalizes far beyond arrays — 'binary search on the answer' solves whole classes of problems.

Mental models

  • Requires sorted input — the invariant that makes halving valid.
  • Watch the boundaries: low ≤ high, and mid = low + (high−low)/2.

Common pitfalls

  • Off-by-one in the loop bound causes infinite loops or missed elements.
  • mid = (low+high)/2 can overflow in fixed-width integers.

Complexity

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)iterative