Binary Search

Binary search halves a sorted array each step to find a target in O(log n), the classic payoff for keeping data ordered.

Halve the search space

Binary search requires a sorted array. It compares the target to the middle element: if they match it is done; if the target is smaller it searches the left half, otherwise the right half. Each comparison discards half the remaining elements, so the search space shrinks geometrically.

Why it is O(log n)

Starting from n candidates and halving each step, the search reaches a single candidate after about log2(n) steps. So binary search runs in O(log n) time, a dramatic improvement over linear search: a billion sorted elements are searched in about thirty comparisons.

• Time: O(log n)
• Extra space: O(1) for the iterative form
• Requires sorted, randomly indexable data
• Best case: O(1) when the middle is the target

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

Getting the boundaries right

Binary search is famously easy to get subtly wrong. The classic bug is computing the midpoint as (lo + hi) that overflows in fixed-width integers; writing lo + (hi - lo)/2 avoids it. Off-by-one errors in the loop bounds are the other common trap. Variants find the first or last occurrence, or the insertion point for a missing key, by adjusting how ties and the final position are handled.

Beyond arrays

The halving idea generalises to binary search on the answer: when a yes/no test is monotonic in a numeric parameter, you can binary-search the parameter itself. This turns many optimisation problems into a search over feasible values.