0

Binary Search

Easy

Halve the search space each step by comparing the target to the midpoint of a sorted range.

divide and conquerlogarithmic
TimeO(log n)
SpaceO(1)
Inputsorted numbers | target
1
0
3
1
5
2
7
3
9
4
11
5
13
6
15
7
17
8
target13

Looking for 13 in a sorted array of 9 values.

steps0
1 / 5
lo = 0; hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if a[mid] == target: return mid
if a[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
Why it matters

Thirty-ish steps cover a billion elements. The bugs all live in the lo, hi and mid updates.

Practise this
Binary SearchESearch Insert PositionEFind First and Last Position of Element in Sorted ArrayM
Keyboard
space play← → stepr restartctrl K search

More in Binary Search

Binary Search on the Answer
O(n log maxPile)
Next visualiser
Binary Search on the Answer