Efficiently find an element in a sorted array by repeatedly halving the search space.
Overview
The one assumption that makes it work
Binary search requires sorted data, and everything it does follows from that. Look at the middle element. If it equals the target, you are done. If it is smaller than the target, then the target cannot be anywhere in the left half either — because everything on the left is smaller still. So discard the entire left half in one comparison, and repeat on the right.
Each comparison eliminates half of what remains. That is the whole idea, and it is why the precondition is non-negotiable: on unsorted data, “smaller than the middle” tells you nothing about which side the target is on.
Parameters
15
Visualization
Step: 0
Enter a target and click Step or Auto-Run.
Algorithm Insight
Binary Search is a Divide and Conquer algorithm.
1.Find the middle bar of the active search range.
2.If $MidHeight = Target$, search complete!
3.If $Target < Mid$, discard everything to the right.
4.If $Target > Mid$, discard everything to the left.
Efficiency
Time ComplexityO(log N)
Space ComplexityO(1)
Binary Search: A Practical Guide
Halve the search space on every comparison. Twenty steps are enough to find one item among a million - provided the array is sorted.
Work one through by hand
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], ten elements, indices 0–9.
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.
example_01.pyPython
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
def correct(a, target):
# returns (index, comparisons)
lo, hi, n = 0, len(a) - 1, 0
while lo <= hi:
mid = lo + (hi - lo) // 2
n += 1
if a[mid] == target:
return mid, n
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, n
def strict_less(a, target):
# BUG 1: `lo < hi` instead of `lo <= hi`
lo, hi = 0, len(a) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print("target correct lo<hi")
for t in arr:
i, _ = correct(arr, t)
print("%6d %7d %5d%s" % (t, i, strict_less(arr, t),
" <-- MISSED" if strict_less(arr, t) == -1 else ""))
# Four of the ten targets are missed and six are found. So a test that
# happens to search for 5, 8, 16, 23, 56 or 72 passes cleanly against a
# function that is wrong for the other four. That is how this bug reaches
# production: not because it is subtle to read, but because it is easy to
# test around.
# BUG 2: dropping the +1 / -1 hangs instead of returning. Run it with a
# step budget rather than letting the page freeze.
def no_adjust(a, target, budget=50):
lo, hi = 0, len(a) - 1
steps = 0
while lo <= hi and steps < budget:
mid = lo + (hi - lo) // 2
if a[mid] == target:
return "found", steps
if a[mid] < target:
lo = mid # should be mid + 1
else:
hi = mid # should be mid - 1
steps += 1
return "gave up", steps
print()
print("no +1/-1, searching for 23:", no_adjust(arr, 23))
print("no +1/-1, searching for 99:", no_adjust(arr, 99))
# The first one still finds 23 -- the bug is invisible when the target is
# present. It is the ABSENT value that spins forever.
print()
print("comparisons, correct version:")
for t in (2, 23, 91, 99):
i, n = correct(arr, t)
print(" target %2d -> index %2d in %d comparisons" % (t, i, n))
# Ten elements, at most four comparisons, and a miss costs the same as a
# hit -- unlike linear search, where a miss is always the worst case.
Output
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.
Where to practise this
Three questions that test the invariant rather than the shape:
The whole algorithm is nine lines, and it prints the window [lo, hi] at every step so you can watch it collapse. The last block searches a million items to show what O(log n) buys.
binary_search.pyPython 3
# Binary search. Precondition: the list is SORTED.
import math
def binary_search(a, target):
lo, hi = 0, len(a) - 1 # inclusive window of candidates
step = 0
while lo <= hi: # <= : a one-item window still needs checking
mid = lo + (hi - lo) // 2 # not (lo + hi) // 2 - see the walkthrough
step += 1
print(f"step {step}: lo={lo:>2} hi={hi:>2} mid={mid:>2} a[mid]={a[mid]:>3}")
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1 # everything left of mid is too small
else:
hi = mid - 1 # everything right of mid is too large
return -1
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("array :", data)
print("target: 23")
print("index :", binary_search(data, 23))
print()
print("target: 7 (not present)")
print("index :", binary_search(data, 7))
print()
big = list(range(1_000_000))
print("searching 1,000,000 items for 999_999")
found = binary_search(big, 999_999)
print("index :", found)
print("worst case, in theory:", math.ceil(math.log2(len(big) + 1)), "comparisons")
Output
How the code works
lo, hi = 0, len(a) - 1The window is inclusive at both ends, so index hi is still a candidate. The other convention — hi = len(a), exclusive — is equally correct, and mixing the two is where most binary search bugs come from.
while lo <= hi:Follows from the window being inclusive. With < instead, a window that has narrowed to a single item is never examined, and a search for the last remaining candidate returns -1.
mid = lo + (hi - lo) // 2Arithmetically the same as (lo + hi) // 2, but that form overflows once lo + hi exceeds the integer width. Python's ints are unbounded so it cannot bite here; in Java it sat undetected in the JDK for nine years.
lo = mid + 1The + 1 is load-bearing. mid has just been compared and ruled out, and leaving it inside the window means a two-item window can stop shrinking — an infinite loop rather than a wrong answer.
return -1The loop ends when lo passes hi, i.e. the window is empty. A failed search costs exactly as much as a successful one, unlike linear search where failure is always the worst case.
Change one thing
Break the precondition: add data.reverse() before the search. It does not raise — it quietly returns the wrong answer, which is the failure mode to be afraid of.
Change hi = mid - 1 to hi = mid and run it. The window stops shrinking and the interpreter is killed after ten seconds. That is the off-by-one, seen from the inside.
Count the steps for 2, for 91 and for 16. The middle element is found instantly and both ends cost the full log n — the exact inverse of linear search.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Binary search on unsorted data:
Nothing checks the precondition. It compares against the middle, discards a half on the strength of that comparison, and returns something plausible - which is far more dangerous than a crash.
Why is the midpoint written mid = lo + (hi - lo) // 2?
Arithmetically identical to (lo + hi) // 2, but that form overflows in fixed-width integers. The bug lived in the JDK's binary search for nine years.
Change hi = mid - 1 to hi = mid and run the program. What happens?
mid has already been compared and ruled out. Leaving it in the window means a two-item window stops shrinking, so the loop never ends.
Cheat sheet
Binary Search
Binary search requires sorted data, and everything it does follows from that. Look at the middle element. If it equals the target, you are done. If it is smaller than the target, then the target cannot be anywhere in the left half either — because everything on the left is smaller still. So discard the entire left half in one comparison, and repeat on the right.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.