Searching
Binary Search Visualiser
Halve the range on every comparison.
Look for 18. This only works because the array is sorted.
- Comparisons
- 0
- for scale
- log₂n ≈ 5
Each comparison throws away half of what is left, so doubling the array adds one comparison rather than twice as many. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.
- Being compared
- Being written
- Pivot or smallest so far
- In its final place
- Ruled out
function binarySearch(a, target) { let lo = 0, hi = a.length - 1; while (lo <= hi) { const mid = (lo + hi) >> 1; if (a[mid] === target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; // not here}The highlighted line is the one that produced the picture on the left.
What Binary Search does
Binary search keeps a range that could still hold the target, marked by lo and hi. It looks at the middle of that range and, because the array is sorted, one comparison tells it which half to throw away. Doubling the array adds one comparison, not n of them.
How it works, step by step
- Set lo to the first index and hi to the last.
- While lo is not past hi, take mid as the middle of the range.
- If the value at mid is the target, stop.
- If it is too small, the target can only be to the right, so move lo past mid. Otherwise move hi before mid.
What to watch for
- Everything the search discards is greyed out, and most of the array is greyed out without ever being looked at. That is the entire trick.
- The comparison counter stops at about log₂n. Twenty cells take five comparisons; a million would take twenty.
- Search for a value that is not there. The range shrinks until lo passes hi, which is the only way the loop can end without a match.
- mid is computed as (lo + hi) >> 1, which rounds down. Getting that rounding wrong is the classic way to write a binary search that loops forever.
Cost
| Best case | O(1) — the first middle |
|---|---|
| Average | O(log n) |
| Worst case | O(log n) |
| Extra space | O(1) |
| Needs sorting | Yes |
When to reach for it
Whenever the data is sorted and will be searched more than once. The idea goes well beyond arrays: anywhere an answer can be tested as “too small” or “too big”, the same halving applies — which is what the binary-search-on-answer pattern is built on.