SearchingSearching

Binary Search

Find a target in a sorted array by repeatedly halving the search range.

Learn Binary Search →
2
0
↑lo
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
↑hi
1/7The array is sorted. Search for 23 in [lo, hi] = [0, 9]; the invariant is that the target, if present, lies inside this range.
Being compared with targetTarget foundEliminated
PseudocodeLearn Binary Search →
1lo = 0, hi = n - 1
2while lo <= hi:
3  mid = lo + (hi - lo) // 2
4  if a[mid] == target: return mid
5  if a[mid] < target: lo = mid + 1
6  else: hi = mid - 1
7return -1
Variables
lo0
hi9
target23
Complexity
best O(1)
avg O(log n)
worst O(log n)
space O(1)
Speed