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

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…