Searching: Linear vs Binary

12.1The game you already played

In week 1 you guessed a number between 1 and 100 by always choosing the middle of the remaining range, and it took at most seven guesses. That is binary search, and it is the second most useful algorithm a beginner can learn (the first is "put it in a dictionary").

Thirty-three questions to find one person on Earth. That column is why O(log n) is treated as "practically free": between a thousand items and a billion, it grows from 10 to 30.

12.2Linear search, for reference

def linear_search(data, target):
    """Return the position of target, or -1. Works on any list."""
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

Worst case n comparisons: O(n). Its virtues are that it needs no preparation and works on unsorted data, which is exactly what you usually have.

12.3Binary search

The rule: look in the middle; if the target is smaller, throw away the right half; if larger, throw away the left half; repeat.

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    steps = 0

    while low <= high:
        steps += 1
        middle = (low + high) // 2

        if data[middle] == target:
            return middle, steps
        elif target < data[middle]:
            high = middle - 1          # drop the right half
        else:
            low = middle + 1           # drop the left half

    return -1, steps

data = list(range(1000000))          # already sorted

print(binary_search(data, 999999))   # (999999, 20)
print(binary_search(data, 0))        # (0, 19)
print(binary_search(data, -5))       # (-1, 19)

At most twenty middle inspections in this million-item list. These exact calls use twenty for the far-end hit and nineteen for the near-end hit and the miss. Compare with linear search, which needs up to a million.

12.4Watch it run: a step-by-step trace

The code is short, but short code hides its behaviour. The cure is to trace it once by hand, writing down low, high and middle at every turn. Take this ten-item sorted list (indices along the top) and search for 23:

Three steps, and each one threw away roughly half of what was left: ten candidates, then five, then two. Now trace a miss — search for 40, which is not in the list:

The loop ends the instant low overtakes high: the window has closed to nothing, so the value cannot be present. That crossing is the whole reason the condition is while low <= high and not < — with <, a one-element window (low == high) is never examined, and a value sitting there is missed.

12.5The off-by-one minefield

Binary search is famous for being easy to describe and hard to get exactly right. Almost every bug is one of three kinds. Here is a version with the classic mistake planted in it — predict what it does before reading on:

def buggy_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        middle = (low + high) // 2
        if data[middle] == target:
            return middle
        elif target < data[middle]:
            high = middle              # BUG: should be middle - 1
        else:
            low = middle + 1
    return -1

Run it on [10, 20] searching for 5. Step 1: low 0, high 1, middle 0, data[0] is 10, and 5 < 10, so high = middle = 0. Step 2: low 0, high 0, middle 0, still 5 < 10, so high = 0 again. Nothing has changed. It loops forever. The fix — high = middle - 1 — guarantees the window shrinks on every branch, so low and high must eventually cross.

The defence is not cleverness, it is a fixed set of tests. Any binary search you write should be tried on: an empty list, a one-item list, a two-item list, the very first element, the very last element, and a value that is absent. Passing these tests is useful evidence, not proof. Justify correctness by showing that all possible answers stay inside the window and that every mismatch strictly shrinks it.

A useful cousin returns not "is it here?" but "where would it go?" — the insertion point. This is what powers bisect in the next section, and it never needs the equality branch at all:

def insertion_point(data, target):
    """First index i such that everything left of i is < target."""
    low, high = 0, len(data)          # note: high starts at len, not len-1
    while low < high:
        middle = (low + high) // 2
        if data[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low

data = [10, 20, 30, 40, 50]
print(insertion_point(data, 30))      # 2  — 30 belongs at index 2
print(insertion_point(data, 35))      # 3  — between 30 and 40
print(insertion_point(data, 99))      # 5  — past the end

Notice the deliberately different shape: high starts at len(data) and the loop is while low < high with high = middle (no −1). The two idioms are not interchangeable — each is internally consistent, and mixing pieces of one into the other is how the bugs above are born. Learn one of each and keep them separate.

12.6But sorting is not free

Binary search costs O(log n) — if the data is already sorted. Sorting costs O(n log n), which is more than a single linear scan. So the arithmetic depends entirely on how many searches you will do.

Notice row three: for repeated plain membership, a set offers average O(1) query time, while binary search offers O(log n); measured constants and preparation still matter. Binary search earns its place when you need order — the nearest value, everything between two dates, the next larger measurement. That is a question a hash table cannot answer at all.

The crossover is worth doing on the back of an envelope. Say sorting a list costs about n log₂ n and each linear scan costs n. Sorting-then-searching for q queries costs roughly n log₂ n + q log₂ n; scanning q times costs q n. For n = 1 000 000, log₂ n ≈ 20, so sorting pays for itself once q climbs past about 20 — after that the scan is throwing away the same million items over and over, while binary search never looks at more than twenty.

12.7Do not write it yourself

Python ships with a tested implementation. Use it in real work; write your own only to understand it, as you did above.

import bisect

data = [10, 20, 30, 40, 50]

i = bisect.bisect_left(data, 30)
print(i, i < len(data) and data[i] == 30)   # 2 True; boundary check also handles empty/missing inputs

print(bisect.bisect_left(data, 35))   # 3 — where 35 would go
bisect.insort(data, 35)               # insert and keep sorted
print(data)                           # [10, 20, 30, 35, 40, 50]

bisect_left is O(log n). insort finds the spot in O(log n) but still has to shift items, so the insertion itself is O(n) — the week 10 lesson has not gone away.

12.8The benchmark

import time, random, bisect

def bench(n, queries=1000):
    data = list(range(n))
    targets = [random.randrange(n) for _ in range(queries)]

    start = time.perf_counter()
    for t in targets:
        linear_search(data, t)
    t_lin = time.perf_counter() - start

    start = time.perf_counter()
    for t in targets:
        bisect.bisect_left(data, t)
    t_bin = time.perf_counter() - start

    lookup = set(data)
    start = time.perf_counter()
    for t in targets:
        t in lookup
    t_set = time.perf_counter() - start

    print(f"n={n:>8}  linear {t_lin:8.4f}s   binary {t_bin:7.5f}s   set {t_set:7.5f}s")

for n in [10000, 100000, 1000000]:
    bench(n)

Three completely different behaviours in one table: linear multiplies by ten each row, binary creeps up by a fifth (that is log n at work), and the set does not move. Everything in this course is visible in those three columns.

12.11Optional Studio Extension

12.12Words from this week

12.13Chapter problem set — Skiena 2.10

Binary search runs on logarithms, so this is the natural week to meet the log rules and a cluster of Skiena's puzzles that all turn on the same idea: halving, and the number of times you can do it. Throughout, lg means log base 2.

import math

x, a, b = 50, 2, 10
print(math.log(x, a))                    # log base 2 of 50
print(math.log(x, b) / math.log(a, b))   # change of base — same value

# identity (d): x**(log_b y) should equal y**(log_b x)
print(3 ** math.log(8, 10))              # 2.6968...
print(8 ** math.log(3, 10))              # 2.6968... — equal

weights = [10] * 10          # ten bags, all 10-gram coins to start
weights[6] = 9               # bag number 7 secretly holds 9-gram coins

# take (i+1) coins from bag i (0-indexed) and weigh them all together
total = sum((i + 1) * weights[i] for i in range(10))
print(550 - total)           # 7  -> the light bag is number 7