How Binary Search Works
Binary search compares the middle element with the target and throws away half the range each time. Twenty comparisons are enough for a million elements — watch it happen, and see the two ways it is usually written wrong.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 6
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 5
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Binary search
- 1
lo = 0; hi = n-1 - 2
while lo <= hi: - 3
mid = (lo + hi) / 2 - 4
if a[mid] == target: return mid - 5
if a[mid] < target: - 6
lo = mid + 1 - 7
else: - 8
hi = mid - 1 - 9
return NOT_FOUND
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(log n) | O(log n) | O(1) |
Requires sorted, randomly accessible data. log₂ of a million is 20, and of a billion is 30 — the whole argument for keeping data sorted.
How binary search works
Binary search keeps a range that must contain the target if it is present at all. It compares the middle element with the target: equal means done, smaller means the answer is in the right half, larger means the left. Each comparison discards half of what is left, so the number of steps is the number of times n can be halved — log₂ n.
- Set low to the first index and high to the last.
- While the range is non-empty, take the middle index.
- If the middle element equals the target, return it.
- If it is smaller than the target, move low past the middle. Otherwise move high before it.
- An empty range means the value is not present — and low is where it would have to be inserted.
Implementation
The same algorithm the visualiser is running, written to be read.
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
# (low + high) // 2 can overflow in fixed-width languages; this cannot.
middle = low + (high - low) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
# low is now the index where the target would be inserted.
return -1When to use it
- Use it on any sorted array you search more than once. It is also the right way to search a sorted column, which is what a database B-tree index is doing.
- Use it beyond arrays: any monotonic predicate can be binary searched — the smallest buffer size that fits, the first version where a test fails, the boundary where a condition flips.
- Avoid it on linked lists, where getting to the middle costs a traversal and the log n advantage disappears.
Check yourself
If the animation made sense, these should too.
Why compute the midpoint as low + (high - low) / 2?
Because (low + high) / 2 overflows once the sum exceeds the integer type's maximum - a bug that sat in the JDK's own binary search for nine years. The subtraction form can never exceed high, so it cannot overflow.
After an unsuccessful binary search, what does `low` tell you?
It is the index where the target would have to be inserted to keep the array sorted. That is why the same routine underlies lower_bound, bisect_left and the insertion point every sorted-collection API returns.