Binary Search
Halve, halve, halve. Each comparison eliminates half the array. log₂(n) comparisons find anything — but only on a sorted list.
- 03
- 17
- 211
- 318
- 424
- 531
- 642
- 755
- 863
- 978
- 1084
- 1191
- 1299
Searching 13 items for 42. Press Step to compare with the middle.
low=0 · high=12 · steps=0
What you just watched
Two pointers — low and high — bracket the part of the array where the target could still be hiding. Each step picks the middle of that window, compares with the target, and throws away whichever half can't possibly contain it. The window shrinks by half every step, so even a million-item list takes at most ~20 comparisons.
Try a target near the start and a target near the end — both take roughly the same number of steps, because halving doesn't care where the answer lives. Then try a target that's not in the array — watch the window collapse to nothing and the algorithm give up cleanly.
For the full Head First treatment of binary search — story, line-by-line walk-through, quiz — head to the concept lesson.