lesson 172 Algorithms & Complexity · advanced

Searching sorted data: binary search and bisect

When data is sorted, a search can look at the middle and throw away half of what is left. A million items take about twenty reads instead of a million.

You'll be able to

Explain why binary search needs sorted data and takes about log2(n) steps
Use bisect_left and bisect_right to find positions and count values in a range
Decide when sorting once and searching many times beats scanning each time

The idea

Finding an invoice number in a list by scanning is O(n). If the list is sorted, you can do what you do with a dictionary or a phone book: open it in the middle, see whether the target is before or after, and discard the other half. Each step halves what is left, so 1,000 items need at most 10 steps and 1,000,000 need at most 20. That growth is O(log n).

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Binary search by hand

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    steps = 0
    while low <= high:
        steps += 1
        middle = (low + high) // 2
        if values[middle] == target:
            return middle, steps
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1, steps

invoices = list(range(489000, 490000))
print(binary_search(invoices, 489737))
print(binary_search(invoices, 489000))
print(binary_search(invoices, 12))

Binary search is only correct on sorted data. On unsorted data it discards the wrong half and reports *not found* for a value that is there. No error is raised, which makes the bug easy to miss.

example-2.py · The same search on unsorted totals

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

totals = [35.84, 91.47, 22.35, 246.6, 54.55]
print(binary_search(totals, 91.47))
print(binary_search(sorted(totals), 91.47))

Python's bisect module does the halving for you. bisect_left(values, x) returns the first position where x could be inserted to keep the list sorted, which is the position of the first value ≥ x. bisect_right(values, x) returns the position after the last value ≤ x. Two calls count the values in a range without looking at each one.

example-3.py · Taxi pickups between 09:00 and 10:05

from bisect import bisect_left, bisect_right

pickups = ["08:02", "08:15", "09:40", "09:58", "10:05", "10:05", "11:30"]
start = bisect_left(pickups, "09:00")
end = bisect_left(pickups, "10:05")
print(start, end, pickups[start:end])
print(bisect_right(pickups, "10:05") - bisect_left(pickups, "10:05"))

When to use it: many lookups in data that changes rarely. Sorting costs O(n log n) once; after that each search is O(log n). For a single lookup in unsorted data, a plain scan (O(n)) is cheaper than sorting first. Mistakes to avoid: searching unsorted data; mixing up bisect_left and bisect_right when values repeat; and slicing or copying the list inside the search, which costs O(n) and wipes out the gain.

Review

Binary search halves a sorted range at each step: O(log n), about 20 steps for a million items.
bisect_left → first position of a value ≥ x; bisect_right → position after the last value ≤ x.
Sort once, search many times; on unsorted data binary search silently gives wrong answers.
Next: hashing finds a value in a set or dictionary without any ordering at all.

Practise this