Binary search
In a sorted array, look at the middle. If it is too small the target must be to the right, if too big to the left. Each look throws away half of what is left.
25812162338567291
Look for 23. Press play or step forward to start.
1function binarySearch(a, target) {2 let lo = 0, hi = a.length - 1;3 while (lo <= hi) {4 const mid = Math.floor((lo + hi) / 2);5 if (a[mid] === target) return mid;6 if (a[mid] < target) lo = mid + 1;7 else hi = mid - 1;8 }9 return -1;10}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the target is the first middle |
| average | log n | any target |
| worst | log n | the target is missing: about 20 probes for a million items |
| space | 1 | just lo, mid and hi |
Where it breaks
- Unsorted input. The whole method rests on "too small means go right". On unsorted data it skips right past the target and says it is missing.
- Off-by-one loops. Use
lo <= hiand move tomid + 1ormid - 1. Mixing styles breaks it:lo < hiwithhi = mid - 1can miss the last item, andlo <= hiwithhi = midcan loop forever. - Duplicates. It returns a matching index, not the first one. Finding the first or last match needs the lower and upper bound variants.