Searching

Linear search checks every element in order — O(n), but works on any iterable, sorted or not.

Binary search only works on sorted data, but is O(log n): compare the target to the middle element, and eliminate half the remaining range every step. That's the same halving idea behind BSTs from the previous course.

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

Python's bisect module does this for you in production code:

import bisect

nums = [1, 3, 5, 7, 9]
bisect.bisect_left(nums, 5)   # 2 — index where 5 is (or would be inserted)
bisect.insort(nums, 6)         # inserts 6 keeping the list sorted

Writing binary search by hand is worth doing once for the mental model — in real code, reach for bisect.