ZERO / HERO
Guessing a number, halving each time

Binary Search

The analogy

I picked a number between 1 and 100. You guess 50; I say "higher". Half the numbers just vanished. Guess 75, "lower" — half again. Seven guesses gets you any number out of a hundred, but only because the numbers are in order.

Visualizer

Watch the range halve

step 1 / 10
LO
1
0
2
1
3
2
4
3
5
4
7
5
8
6
HI
9
7

Sorted first — without that, none of this is allowed. Hunting for 37.8 values, target 37

📖 In depth — the full reference

Binary search — everything worth knowing

factvaluenote
timeO(log n)a billion items in 30 probes; each probe kills half
requirementSORTED data + O(1) random accessa sorted linked list is useless — no O(1) jump to the middle
loop invarianttarget, if present, is inside [lo, hi]every correct variant defends exactly this
classic bug #1lo < hi vs lo <= hioff-by-one: <= is right for the closed-interval version
classic bug #2mid = (lo+hi)/2 overflowa REAL bug in Java's stdlib for 9 years; Python ints can't overflow, JS is safe below 2^53
variantsfirst/last occurrence, insertion pointkeep searching after a hit — "bisect_left vs bisect_right"
generalisationbinary search on the ANSWERany monotonic yes/no question: "smallest capacity that ships in D days" — Module 7 territory

Python: bisect, the stdlib binary search

import bisect
xs = [3, 7, 11, 18, 24, 31, 42]
i = bisect.bisect_left(xs, 18)     # 3 — leftmost insertion point
found = i < len(xs) and xs[i] == 18  # membership test, O(log n)

# bisect_left vs bisect_right on duplicates:
ds = [1, 3, 3, 3, 9]
print(bisect.bisect_left(ds, 3))    # 1 — before the run of 3s
print(bisect.bisect_right(ds, 3))   # 4 — after the run
# right - left == how many 3s. Grade lookup, timestamp windows,
# "closest value" — all bisect one-liners.
def binary_search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[mid] < t:
            lo = mid + 1      # left half impossible
        else:
            hi = mid - 1      # right half impossible
    return -1

import bisect            # the stdlib version
bisect.bisect_left(a, t)
Check yourself

Binary search on an unsorted array…

Practice — write it yourself

binary_search(sorted_arr, t): lo/hi bounds, probe the middle with (lo + hi) // 2, discard half each step. Return the index or -1. Watch the boundaries!

Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser