Searching Concepts

Searching means locating a value, or a position that satisfies some condition, inside a collection of data. "Is this value present?", "Where is it?", and "What is the first element greater than or equal to this value?" are all search questions. This chapter introduces linear search and binary search, then the wider family built on binary search: searching on the answer (parametric search), ternary search, and hash-based lookup. Along the way it fixes the vocabulary used in the rest of the guide.

Linear search

Linear (sequential) search compares elements one by one from the front. It needs no ordering and works on anything you can only read front to back, such as linked lists or streams. The price is that in the worst case it inspects every element, so the time grows in proportion to the number of elements n.

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


print(linear_search([7, 3, 9, 3], 3))   # 1 (first occurrence)
print(linear_search([7, 3, 9, 3], 4))   # -1

Python's x in list and list.index(x) are linear searches under the hood. For a few dozen elements that is perfectly fine; sorting or building an index would cost more than it saves.

Binary search

Binary search works on sorted arrays. It compares the target with the middle element and throws away the half that cannot contain it, over and over. Each comparison halves the candidate range, so even a million elements take only about 20 steps. The essential precondition is order, or more generally monotonicity: a condition whose truth value flips exactly once along the range.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1          # closed interval [lo, hi]
    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


print(binary_search([2, 5, 8, 12, 16, 23], 16))   # 4

This version only tells you whether a value exists. When the value occurs several times, which index you get back is unspecified. In practice the boundary-finding forms in the next section, lower_bound and upper_bound, are used far more often.

Finding boundaries: lower_bound and upper_bound

• lower_bound(x): the first index i with a[i] >= x, or len(a) if there is none.
• upper_bound(x): the first index i with a[i] > x, or len(a) if there is none.
• The difference upper_bound(x) - lower_bound(x) is the number of occurrences of x.
• lower_bound(x) is also the leftmost slot where x can be inserted without breaking the order.

Python's standard bisect module provides exactly these two functions: bisect_left is lower_bound and bisect_right is upper_bound.

from bisect import bisect_left, bisect_right

scores = [10, 20, 20, 20, 35, 50]
print(bisect_left(scores, 20))    # 1
print(bisect_right(scores, 20))   # 4
print(bisect_right(scores, 20) - bisect_left(scores, 20))   # 3 occurrences
print(bisect_left(scores, 99))    # 6 (the end)

Monotone predicates and searching on the answer

Binary search is not limited to arrays. If a condition P(k) over an integer range is false up to some boundary and true from then on (False, False, ..., True, True), binary search finds the first k where it becomes true. This is called parametric search, or "binary searching the answer". The trick is to turn an optimization question such as "what is the smallest daily throughput that meets the deadline?" into a yes/no question: "is this value enough?"

Ternary search finds the position of the maximum or minimum of a unimodal function, one that rises and then falls (or the reverse). It splits the range into thirds, compares the function at two inner points, and discards the third that cannot contain the extremum.

Hash lookup

A hash table (Python's set and dict) turns a key into a hash and jumps straight to its slot, answering "is it present?" in O(1) on average. It keeps no ordering, though, so it cannot answer "the first value at least x" or "all values in [a, b]". Use hashing for exact-match lookups and sorting plus binary search when order or ranges matter.

Vocabulary

Summary

• Linear search is the simplest choice for small or unsorted data.
• Binary search runs in O(log n) on sorted data, and its boundary forms, lower_bound and upper_bound, are the most useful.
• With a monotone predicate you can binary search the answer itself, no array required.
• Use hashing for exact matches; use sorting plus binary search for ordered and range queries.