Efficiently find an element in a sorted array by repeatedly halving the search space.
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)
Overview
Linear search checks every element in order and takes O(n) comparisons. Binary search takes O(log n) by cutting the search space in half on every step. On a million elements, that is 20 comparisons instead of a million — but it only works if the data 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).
Experiments to try with Binary Search
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.
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.
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.
Continue with linear search, which builds on this idea.
Run it in Python
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.
Predict, then reveal
About to run: Count the halvings. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
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
Halve the search space with every comparison and watch binary search locate a target in a sorted array in log n steps.
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.