Searching: linear and binary

Finding something is the most common thing a program does. If the data is unsorted, the only honest answer is to look at every element until you find it — $O(n)$. But if the data is sorted, each look can discard half of what remains, and a billion elements take only about thirty comparisons.

Pick a target below and step through the shrinking window.

Linear search #

Walk the array from the front, comparing as you go, and stop on a match:

def linear_search(a, target):
    for i, value in enumerate(a):
        if value == target:
            return i
    return -1

The cost is $O(n)$: in the worst case the target is last or absent. It needs no precondition, works on linked lists and streams, and is the only option when the data is unordered.

Binary search #

Maintain a range [lo, hi] and test its midpoint:

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Each iteration halves the range, so the loop runs at most $\lfloor \log_2 n \rfloor + 1$ times. For $n = 10^9$ that is about thirty comparisons instead of a billion.

Choosing, and the alternative #

• Unsorted data, searched once: linear scan.
• Sorted data, searched many times: binary search.
• Repeated lookups keyed by value: build a hash table once and search in $O(1)$ average. Sorting plus binary search costs $O(n \log n)$ to set up and $O(\log n)$ per query; a dict costs $O(n)$ to build and $O(1)$ per query when keys are hashable.

Python exposes binary search directly through bisect, including bisect_left/bisect_right for insertion points.

Where next: graph traversal — searching an entire network of nodes, not just a list.