Searching Algorithms & Binary Search Variants

Linear Search

Check every element, one at a time, until the target turns up or the list runs out. It makes no assumptions about order, so it works on any list, sorted or not, but in the worst case (the target is last, or missing entirely) it costs O(n).

def linear_search(items: list[int], target: int) -> int:
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1

print(linear_search([4, 2, 9, 1, 7], 9))
print(linear_search([4, 2, 9, 1, 7], 5))

2
-1

Binary Search

If the list is sorted, there's no need to check every element. Compare the target to the middle element: if they match, done. If the target is smaller, it can only be in the left half, if larger, only the right half, so the other half is discarded without ever being examined. Each comparison cuts the remaining search space in half, giving O(log n), exactly Lesson 1's logarithmic growth class.

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

print(binary_search([1, 3, 5, 7, 9, 11, 13], 7))
print(binary_search([1, 3, 5, 7, 9, 11, 13], 2))

3
-1

The two-line loop is easier to believe when you watch the window shrink. Searching for 9 takes just three steps: each one tests the midpoint, then throws away the half that cannot contain the target.

The same halving logic reads naturally as recursion too, each call searches a strictly smaller [low, high] range until it either finds the target or the range goes empty:

def binary_search_recursive(
    items: list[int], target: int, low: int = 0, high: int | None = None
) -> int:
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    elif items[mid] < target:
        return binary_search_recursive(items, target, mid + 1, high)
    else:
        return binary_search_recursive(items, target, low, mid - 1)

print(binary_search_recursive([1, 3, 5, 7, 9, 11, 13], 11))

5

Finding the First and Last Occurrence

Plain binary search stops at the first match it stumbles into, which is fine when values are unique, but with duplicates that match could be anywhere in a run of equal values. Finding the first or last occurrence just adds one twist: instead of returning immediately on a match, record it and keep narrowing toward that end of the range.

def find_first_occurrence(items: list[int], target: int) -> int:
    low, high = 0, len(items) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            result = mid
            high = mid - 1       # record it, but keep searching left for an earlier match
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

def find_last_occurrence(items: list[int], target: int) -> int:
    low, high = 0, len(items) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            result = mid
            low = mid + 1        # record it, but keep searching right for a later match
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

data = [1, 2, 2, 2, 3, 4]
print(find_first_occurrence(data, 2))
print(find_last_occurrence(data, 2))

1
3

Python's bisect module already implements this exact idea in C, and adds an insertion-point variant useful for keeping a list sorted as new values arrive:

import bisect

data = [1, 3, 3, 3, 5, 7, 9]
print(bisect.bisect_left(data, 3))    # first index where 3 could be inserted
print(bisect.bisect_right(data, 3))   # last index where 3 could be inserted

bisect.insort(data, 4)                # insert 4 while keeping the list sorted
print(data)

1
4
[1, 3, 3, 3, 4, 5, 7, 9]

bisect_left and bisect_right return where a value could be inserted, not necessarily where it already is, which is why they work correctly even when the target isn't present at all. insort combines that insertion point with an actual insert, giving O(n) overall (an O(log n) search plus an O(n) shift, Lesson 2's insertion cost) rather than resorting the whole list.

Searching a Rotated Sorted Array

A sorted array that's been rotated, like [4, 5, 6, 7, 0, 1, 2] (the sorted array [0, 1, 2, 4, 5, 6, 7] rotated left by four positions), isn't fully sorted anymore, so plain binary search can't run directly on it. But at every midpoint, at least one of the two halves is guaranteed to still be fully sorted. Check which half that is, then check whether the target falls inside that sorted half's range to decide which side to keep, still cutting the search space in half every step.

def search_rotated_sorted_array(items: list[int], target: int) -> int:
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[low] == items[mid] == items[high]:
            # can't tell which half is sorted when the endpoints and
            # midpoint all match, so shrink the range by one on each side
            low += 1
            high -= 1
        elif items[low] <= items[mid]:             # left half is sorted
            if items[low] <= target < items[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:                                       # right half is sorted
            if items[mid] < target <= items[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

rotated = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated_sorted_array(rotated, 0))
print(search_rotated_sorted_array(rotated, 3))

4
-1

With distinct values this runs in O(log n), the same halving idea as ordinary binary search, just with an extra check up front at each step to work out which half is safe to reason about. Duplicate values complicate that check: if items[low], items[mid], and items[high] all happen to match, there's no way to tell which half is sorted from the endpoints alone, so the code above falls back to shrinking the range by one from each end until that ambiguity clears. That fallback is still correct, just no longer a clean halving, an array of all-identical values with one different value hidden in the middle forces it all the way down to O(n).

Complexity at a Glance

Best case O(1) happens when the very first element checked (the middle, for the binary variants) happens to be the target. Every binary-search-family algorithm here needs O(1) extra space beyond the input, no new data structures, just a shrinking[low, high] range (or O(log n) stack space for the recursive version).