Python Linear and Binary Search

Linear search walks through the items from the start until it finds the target or runs out:

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

photos = [52, 11, 39, 24, 18]          # unsorted is fine
print(linear_search(photos, 24))       # 3
print(linear_search(photos, 99))       # -1

It needs no preparation and works on unsorted data, any iterable, and with any condition, such as "first photo taken after 6 pm". Its cost grows with the list: the worst case, a missing target, checks every item.

Python's built-ins are linear searches: target in items, items.index(target) (which raises ValueError if missing) and next((x for x in items if condition), None). For a single search on a small or unsorted list, linear search is the right choice. For many searches, consider sorting once and using binary search, or putting the values in a set or dictionary for O(1) average lookups.

Binary search compares the target with the middle item. Because the list is sorted, everything to the left is smaller and everything to the right is larger, so one comparison eliminates half the remaining items:

search 39 in [11, 18, 24, 39, 52]
middle 24 < 39  → discard 11, 18, 24 → [39, 52]
middle 39 == 39 → found

The ordering is what makes discarding safe. On unsorted data, the target could be in the half that was thrown away, so binary search can miss items that are present, without any error to warn you.

The list must be sorted by the same key you search with. A list of photos sorted by date can't be binary-searched by id. If data changes often, keeping it sorted costs time on every insert, so binary search pays off when you search much more often than you modify.

A correct binary search maintains an invariant: if the target is present, it lies within the current interval. The half-open convention [low, high), which includes low and excludes high, is the easiest to get right:

def binary_search(items, target):
    low, high = 0, len(items)            # interval [low, high)
    while low < high:                    # non-empty interval
        mid = (low + high) // 2
        if items[mid] < target:
            low = mid + 1                # target is right of mid
        elif items[mid] > target:
            high = mid                   # target is left of mid
        else:
            return mid
    return -1

Each branch keeps the invariant: when items[mid] < target, mid and everything before it can't be the answer, so low moves past it. The loop ends when the interval is empty.

Most binary search bugs come from mixing conventions: using high = len(items) - 1 (inclusive) with while low < high, or high = mid - 1 with a half-open interval. The result is an infinite loop or a missed first or last element. Test empty lists, one-element lists, and targets at both ends and absent.

The bisect module implements binary search in C. Its functions return insertion positions: where a value would go to keep the list sorted.

from bisect import bisect_left, bisect_right, insort
photos = [11, 18, 24, 24, 39]
print(bisect_left(photos, 24))    # 2: before existing 24s
print(bisect_right(photos, 24))   # 4: after existing 24s
print(bisect_left(photos, 30))    # 4: where 30 would go
insort(photos, 30)                # insert keeping order

An insertion position isn't proof the value exists: bisect_left(photos, 30) returns 4 even though 30 wasn't there. Always check: i < len(photos) and photos[i] == target.

bisect_right - bisect_left counts how many times a value appears, and the pair finds ranges, such as every photo id between 20 and 40. Since Python 3.10, the functions accept key= to search records by one field, provided the list is sorted by that same key.

Task: implement a linear search and a binary search and test empty input, absent values and end positions.

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

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

cases = [([], 5, -1), ([7], 7, 0), ([3, 8, 12, 20], 3, 0),
         ([3, 8, 12, 20], 20, 3), ([3, 8, 12, 20], 10, -1)]
for items, target, expected in cases:
    assert linear_search(items, target) == binary_search(items, target) == expected
print("all", len(cases), "cases pass")

Both functions agree on every edge case, including the empty list and targets at each end. For the worked check, binary search requires a suitably sorted search space, ordered by the same key you search with.

The bisect module documentation includes recipes for searching sorted lists. Continue with sorting algorithms and hash tables. Practise with the Python exercises and Python quiz.