Big-O and searching

What Big-O measures

An algorithm is a step-by-step method for solving a problem. Big-O notation describes how the number of steps grows when the input size grows. The input size is called n: the number of items in the list, students in the class, rows in the file. Big-O ignores small details and constant factors; it only cares about the shape of the growth.

Linear search

Linear search starts at the first item and checks each one until it finds the target or reaches the end. It works on any list, sorted or not. In the worst case (the item is last or missing) it checks all n items, so it is O(n).

def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1                   # not found

roll_numbers = [104, 87, 230, 15, 66]
print(linear_search(roll_numbers, 15))    # 3
print(linear_search(roll_numbers, 999))   # -1

Binary search, step by step

Binary search only works on a sorted list, but it is dramatically faster. It looks at the middle item. If that is the target, done. If the target is smaller, the answer must be in the left half; if bigger, in the right half. Each step throws away half of what is left, so a million items need only about 20 steps. That is O(log n).

1. Sorted list: [3, 8, 15, 23, 42, 57, 61, 78, 90]. Target: 61. low = 0, high = 8.
2. Middle index (0 + 8) // 2 = 4, value 42. 61 is bigger, so low = 5.
3. Middle index (5 + 8) // 2 = 6, value 61. Found it at index 6 after only 2 looks.
4. If low ever becomes greater than high, the target is not in the list.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1          # target is in the right half
        else:
            high = mid - 1         # target is in the left half
    return -1

data = [3, 8, 15, 23, 42, 57, 61, 78, 90]
print(binary_search(data, 61))   # 6
print(binary_search(data, 5))    # -1

The bisect module

Python's standard library already has binary search in the bisect module. bisect_left(a, x) returns the position where x would go in the sorted list a, to the left of any equal items. insort(a, x) inserts x in the right place so the list stays sorted.

from bisect import bisect_left, bisect_right, insort

marks = [35, 48, 52, 52, 67, 80, 91]
i = bisect_left(marks, 52)
print(i, marks[i] == 52)                 # 2 True: found
print(bisect_right(marks, 52) - bisect_left(marks, 52))   # 2 students got 52
insort(marks, 75)
print(marks)                             # 75 lands in the right place

Why sets and dicts are so fast

Sets and dicts use hashing. A hash function turns a key into a number, and that number says almost exactly where the item is stored. So checking "is x in my_set?" jumps straight to the right place instead of walking the whole collection. On average it is O(1), no matter how big the set is.

import time

ids_list = list(range(100_000))
ids_set = set(ids_list)

start = time.perf_counter()
for _ in range(100):
    -1 in ids_list                       # walks all 100,000 items each time
list_ms = (time.perf_counter() - start) * 1000

start = time.perf_counter()
for _ in range(100):
    -1 in ids_set                        # one jump each time
set_ms = (time.perf_counter() - start) * 1000

print("list:", round(list_ms, 2), "ms   set:", round(set_ms, 4), "ms")