Searching

Linear search is the obvious way to find something: check the items one by one until you find it or run out. It works on any list and takes O(n) steps in the worst case.

If the list is sorted, you can do much better. Binary search looks at the middle item. If that's the target, done. If the target is smaller, it must be in the left half; if bigger, the right half. Throw the other half away and repeat. It's how you'd look up a word in a paper dictionary.

def binary_search(xs, target):
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

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

Each step halves what's left, so it's O(log n): 1,000 items need at most 10 checks, a million about 20, a billion about 30. The catch is that the list must be sorted first, and it must allow jumping to the middle (an array, not a linked list).

The rule of thumb: search once, use linear search. Search many times, sort once and use binary search, or put the items in a set or dictionary.