Work one through by hand
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], ten elements, indices 0–9.
lo=0, hi=9 → mid=4 → a[4]=16 < 23 → go right, lo=5
lo=5, hi=9 → mid=7 → a[7]=56 > 23 → go left, hi=6
lo=5, hi=6 → mid=5 → a[5]=23 → found, index 5
Three comparisons against a linear search’s six. The gap is unremarkable at ten elements and decisive at a million: linear search averages 500,000 comparisons, binary search takes at most 20.
Where log n comes from
The search space starts at n and halves every step: n, n/2, n/4, n/8, and so on. The search ends when one element is left, so the question is how many halvings that takes:
n / 2k = 1 → 2k = n → k = log2(n)
That is the definition of a logarithm, not an analogy for it. Doubling the array adds exactly one comparison. Going from 1,000 to 1,000,000 elements — a thousandfold increase — adds ten.
Halving the search space
Binary search finds a value in a sorted array by repeatedly discarding half of it.
Look at the middle element. If it matches, done. If the target is smaller, everything from the middle rightwards is irrelevant. If larger, everything leftwards is. Repeat on what remains.
Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:
| Step | Range | Middle | Comparison |
|---|
| 1 | 0–9 | 16 (index 4) | 23 > 16, search right |
| 2 | 5–9 | 38 (index 7) | 23 < 38, search left |
| 3 | 5–6 | 23 (index 5) | Found |
Three comparisons for ten elements. Linear search would have taken six.
The scaling is what makes it important:
| Array size | Linear search | Binary search |
|---|
| 100 | 100 | 7 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
Thirty comparisons for a billion items. That is the practical meaning of O(log n).
Getting it right
Binary search is famously easy to write incorrectly — a well-known observation is that a large share of published implementations contained bugs for years.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi: # <= not <, or the last element is missed
mid = lo + (hi - lo) // 2 # avoids overflow in fixed-width languages
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1 # +1, or it can loop forever
else:
hi = mid - 1 # -1, same reason
return -1
Four details in those eight lines are the ones that go wrong:
lo <= hi, not lo < hi. With <, a single-element range is never examined.
mid + 1 and mid - 1. Without the adjustment, a two-element range can fail to shrink and the loop never terminates.
lo + (hi - lo) // 2 rather than (lo + hi) // 2. In Python integers are unbounded so it does not matter; in C or Java the sum can overflow, and this was a real bug in widely-used library code.
The array must be sorted. On unsorted input it returns a wrong answer silently, which is worse than failing.
In practice, use the standard library: Python's bisect_left and bisect_right are correct, tested and C-speed.
The three off-by-one details, demonstrated
The article says binary search is famously easy to write incorrectly and names the details that break it. Here are the broken versions next to the correct one, on inputs chosen so that the difference actually shows -- because the usual mistake is that the buggy version passes every test you happen to try.
Experiments to try
- Count the halvings. Set Array Size to 25 and press Next Step repeatedly, watching the shaded region shrink. It takes about five steps, because 25 = 32 is the first power of two above 25.
- Double the array, add one step. Run a search at Array Size 12 and count the steps. Now set it to 24 and count again. One extra step, not twice as many — that is the logarithm, visible directly.
- Search for something absent. Set Search Target to a value not in the array. The window still collapses in log n steps; a failed binary search costs the same as a successful one, unlike linear search where failure is always the worst case.
- Find the expensive targets. Press Reset Array and try searching for the very first and very last elements. Both take the full log n steps, while the middle element is found immediately — the exact inverse of linear search’s cost profile.
Traps worth knowing
- Integer overflow in the midpoint. Writing mid = (lo + hi) / 2 overflows when lo and hi are large. Use mid = lo + (hi − lo) / 2. This bug sat in the JDK’s binary search for nine years.
- Off-by-one in the bounds. The two conventions — inclusive hi = n − 1 with while (lo <= hi), or exclusive hi = n with while (lo < hi) — are both correct, and mixing them gives an infinite loop or a missed last element. Pick one and keep it.
- Assuming the array is sorted. Binary search on unsorted data does not error; it silently returns wrong answers, which is far worse. If sortedness is an assumption rather than an invariant, it will eventually be violated.
- Wanting the first duplicate. Plain binary search returns some match, not the leftmost. Finding the first occurrence needs the variant that keeps searching left after a hit instead of returning.
The short version
Binary search converts a sorted array into an O(log n) lookup by throwing away half the remaining candidates with every comparison. The cost is the precondition: something must keep the data sorted, and if that guarantee ever lapses the algorithm fails silently rather than loudly. Sort once and search many times and it is close to unbeatable; sort in order to search once and you have spent O(n log n) to save O(n).
The variants that matter more than the basic version
Finding an exact match is the least useful form. The valuable variants find boundaries.
Leftmost insertion point (bisect_left) — the first position where the target could be inserted keeping the array sorted. With duplicates, this is the first occurrence.
Rightmost insertion point (bisect_right) — one past the last occurrence.
Together they give the range of a duplicated value, and therefore its count, in O(log n):
from bisect import bisect_left, bisect_right
lo = bisect_left(arr, target)
hi = bisect_right(arr, target)
count = hi - lo # occurrences of target
exists = lo < len(arr) and arr[lo] == target
First element ≥ target is bisect_left; last element ≤ target is bisect_right(arr, target) - 1. Those two cover most real uses — finding the price band, the applicable tax bracket, the most recent record before a timestamp.
Binary search on an answer
The most powerful application is not searching an array at all. If a problem has a monotonic predicate — something that is false up to a threshold and true after it — you can binary search for the threshold.
"What is the minimum ship capacity needed to deliver all packages within D days?"
Capacity is monotonic: if capacity C works, so does C+1. So binary search over capacity, and for each candidate check feasibility in O(n):
def min_capacity(weights, days):
def feasible(cap):
used, load = 1, 0
for w in weights:
if load + w > cap:
used, load = used + 1, 0
load += w
return used <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid might be the answer, keep it
else:
lo = mid + 1
return lo
Note the different loop shape: lo < hi and hi = mid rather than mid - 1, because we are converging on a boundary rather than looking for a match. That is the template for this whole family of problems, and it is worth memorising separately from the exact-match version.
Where it is used
- Database indexes. A B-tree is binary search generalised to disk pages.
bisect.insort for maintaining a sorted list.- Version bisection —
git bisect is binary search over commits. - Numerical root finding — bisection on a continuous function.
- Rate limiting and capacity planning — the answer-search pattern above.
- Timestamp lookups in log and time-series data.
Questions people ask
Does the array have to be sorted? Yes. On unsorted input it returns a wrong answer without any error.
Is sorting first worth it? For one search, no — sorting is O(n log n) and a linear scan is O(n). For many searches on the same data, absolutely.
What about duplicates? Plain binary search finds some occurrence. Use bisect_left and bisect_right for the first, last, or count.
Why is it so easy to get wrong? The off-by-one boundaries. Use the standard library, or memorise one template and reuse it.
Can it work on a linked list? Not usefully — reaching the middle requires walking there, which is O(n) per step and destroys the advantage.
What is interpolation search? A variant that guesses the position from the value's magnitude, assuming a uniform distribution. O(log log n) when the assumption holds and O(n) when it does not.
Recap in one screen
- Halve the search space each comparison: 30 steps for a billion sorted items.
- The array must be sorted, or the result is silently wrong.
lo <= hi, mid + 1, mid - 1 — the three off-by-one details that break implementations.- The useful variants find boundaries, not exact matches;
bisect_left and bisect_right give first, last and count. - Binary searching an answer works whenever feasibility is monotonic, and it is the most powerful form.