Binary Search

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

Binary Search. Given a sorted list of numbers and a target, return the target's index, or minus one if it isn't there.

Here are fifteen numbers in order, and the target is seventy-two.

You could check every number, starting from the left. That's a linear scan: up to n checks. A million numbers could take a million steps.

But the list is sorted, so check the middle instead. If the middle is too small, the target can only be on its right, so throw away the whole left half. Too big? Throw away the right half. Every check cuts what's left in half.

In code, two pointers, lo and hi, mark the part that's still alive. While lo is at most hi, mid is their average, rounded down. If it's the target, return mid. If it's smaller, move lo past mid. If it's bigger, move hi below mid. When lo passes hi, nothing is left, so return minus one.

Let's find seventy-two. Lo is zero and hi is fourteen, so mid is seven: forty-one. Too small, so the left half falls away, and lo becomes eight. Now mid is eleven: eighty. Too big, so hi drops to ten. Mid is nine: sixty-four. Too small, so lo becomes ten. Mid is ten: seventy-two. Found it, in four steps.

Each step halves what's left, so the time is O of log n. About twenty steps for a million numbers, and only thirty for a billion. The space is constant: just three pointers.

Check the middle, drop half, repeat. That's Binary Search.