Searching Algorithms

Linear search

def linear_search(items, target):
    """Return the index of target, or -1. O(n)."""
    for index, item in enumerate(items):
        if item == target:
            return index
    return -1


values = [4, 2, 9, 7, 1]
print(linear_search(values, 9))       # 2
print(linear_search(values, 5))       # -1

# In practice, Python already has this
print(values.index(9) if 9 in values else -1)
print(next((i for i, v in enumerate(values) if v == 9), -1))

• Works on any sequence, sorted or not.
• O(n): on average it checks half the items, and all of them when the target is absent.
• For a one off search on unsorted data, this is the correct algorithm.

Binary search

def binary_search(items, target):
    """Return the index of target in a SORTED list, or -1. O(log n)."""
    low, high = 0, len(items) - 1

    while low <= high:
        middle = (low + high) // 2
        if items[middle] == target:
            return middle
        if items[middle] < target:
            low = middle + 1              # discard the left half
        else:
            high = middle - 1             # discard the right half

    return -1


values = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(values, 7))       # 3
print(binary_search(values, 4))       # -1

searching for 11 in [1, 3, 5, 7, 9, 11, 13]

step 1   [1, 3, 5, 7, 9, 11, 13]      middle = 7,  7 < 11, keep the right
                     ^
step 2   [9, 11, 13]                  middle = 11, found
             ^

Each step throws away half the remaining items. A million items need about twenty steps; a billion need about thirty.

The recursive form

def binary_search_recursive(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1

    middle = (low + high) // 2
    if items[middle] == target:
        return middle
    if items[middle] < target:
        return binary_search_recursive(items, target, middle + 1, high)
    return binary_search_recursive(items, target, low, middle - 1)


print(binary_search_recursive([1, 3, 5, 7, 9], 9))     # 4

Two classic bugs: writing while low < high, which misses the final single element; and forgetting the + 1 or - 1, which loops forever. Test with a list of one item and with a target that is absent.

The standard library does this

import bisect

values = [1, 3, 5, 7, 9, 11]

print(bisect.bisect_left(values, 7))       # 3 - the insertion point
print(bisect.bisect_right(values, 7))      # 4


def index_of(items, target):
    """Binary search using bisect."""
    position = bisect.bisect_left(items, target)
    if position < len(items) and items[position] == target:
        return position
    return -1


print(index_of(values, 7), index_of(values, 8))     # 3 -1


ordered = [1, 5, 9]
bisect.insort(ordered, 7)                  # insert, keeping the order
print(ordered)                              # [1, 5, 7, 9]

Variants worth knowing

The first and last occurrence

def first_occurrence(items, target):
    low, high, result = 0, len(items) - 1, -1
    while low <= high:
        middle = (low + high) // 2
        if items[middle] == target:
            result = middle
            high = middle - 1              # keep looking to the LEFT
        elif items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return result


def last_occurrence(items, target):
    low, high, result = 0, len(items) - 1, -1
    while low <= high:
        middle = (low + high) // 2
        if items[middle] == target:
            result = middle
            low = middle + 1               # keep looking to the RIGHT
        elif items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return result


values = [1, 2, 2, 2, 3, 4]
print(first_occurrence(values, 2), last_occurrence(values, 2))     # 1 3
print(last_occurrence(values, 2) - first_occurrence(values, 2) + 1) # 3 - the count

Searching a rotated list

def search_rotated(items, target):
    """A sorted list rotated at an unknown point. Still O(log n)."""
    low, high = 0, len(items) - 1

    while low <= high:
        middle = (low + high) // 2
        if items[middle] == target:
            return middle

        if items[low] <= items[middle]:          # the left half is sorted
            if items[low] <= target < items[middle]:
                high = middle - 1
            else:
                low = middle + 1
        else:                                     # the right half is sorted
            if items[middle] < target <= items[high]:
                low = middle + 1
            else:
                high = middle - 1

    return -1


print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))     # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))     # -1

Binary search on an answer

def integer_square_root(n):
    """The largest x with x * x <= n, without using sqrt."""
    if n < 2:
        return n
    low, high = 1, n // 2
    while low <= high:
        middle = (low + high) // 2
        square = middle * middle
        if square == n:
            return middle
        if square < n:
            low = middle + 1
        else:
            high = middle - 1
    return high


for n in [16, 17, 24, 100]:
    print(n, integer_square_root(n))

Binary search is not only for lists. Whenever a condition is false up to some point and true afterwards, you can search the answer space in logarithmic time.

When to use which

import time
import random
import bisect

data = sorted(random.sample(range(10_000_000), 200_000))
targets = random.sample(data, 500)

start = time.perf_counter()
for target in targets:
    data.index(target)                          # linear
print(f"linear: {time.perf_counter() - start:.4f}s")

start = time.perf_counter()
for target in targets:
    bisect.bisect_left(data, target)            # binary
print(f"binary: {time.perf_counter() - start:.4f}s")

lookup = set(data)
start = time.perf_counter()
for target in targets:
    target in lookup                            # hash
print(f"set:    {time.perf_counter() - start:.4f}s")

If you need repeated lookups and do not need ordering, a set beats binary search outright. Reach for binary search when the data is already sorted, or when you need the position rather than a yes or no.

Searching structured data

import bisect

records = sorted(
    [{"id": i, "name": f"user{i}"} for i in range(0, 1000, 7)],
    key=lambda r: r["id"],
)
keys = [r["id"] for r in records]          # a parallel key list


def find_record(target_id):
    position = bisect.bisect_left(keys, target_id)
    if position < len(keys) and keys[position] == target_id:
        return records[position]
    return None


print(find_record(700))
print(find_record(701))

# For repeated lookups, an index is simpler and faster
index = {r["id"]: r for r in records}
print(index.get(700))

Common mistakes

• Running binary search on unsorted data. It returns wrong answers silently.
• Writing while low < high and missing the last element.
• Forgetting middle + 1 or middle - 1, causing an infinite loop.
• Sorting a list once in order to perform a single search.
• Using list.index repeatedly inside a loop.
• Comparing floats for exact equality during a search.

Best practices

• Use in and index for small or one off searches.
• Use a set or dict for repeated membership tests.
• Use bisect rather than writing binary search, unless you are practising.
• Test every search with an empty list, one item, the first item, the last item and a missing item.
• Remember that binary search applies to answers, not only to lists.

Practice

1. Implement binary search iteratively and recursively, and test both on the edge cases.
2. Count how many times a value appears in a sorted list in O(log n).
3. Find the insertion point for a new value in a sorted list without bisect.
4. Find the smallest value in a rotated sorted list.
5. Use binary search on an answer to find the smallest divisor meeting a condition.

Conclusion

Linear search always works and costs O(n). Binary search needs sorted data and costs O(log n). A hash lookup costs O(1) and needs neither ordering nor a search. Choose by what the data already is, not by which algorithm is more interesting.