Binary Search

Binary search is the fastest way to find a value in a sorted array. Instead of scanning element by element, you jump straight to the middle, ask "is my target bigger or smaller than this?", and throw away the half that cannot contain it. Repeat, and the search space collapses by half every single step.

The idea

Keep a window [lo, hi] that must contain the target. Look at the middle of the window. If the middle is the target, you are done. If the target is bigger, it must be in the right half, so move lo past the middle. If it is smaller, it must be in the left half, so move hi before the middle. Each comparison halves the window.

Because every round throws away half of what is left, an array of one million items takes only about 20 comparisons. That halving is the whole magic.

Walk through it

Press Play on the right, or step with Next / Back. We are searching for 16 in [2, 5, 8, 12, 16, 23, 38, 56]. Notice three things:

• The mid cell turns blue when we compare it to the target.
• The half we rule out turns gray (dimmed) and is never touched again.
• When a[mid] finally equals the target, that cell turns green — found.

The search window shrinks from 8 cells, to 4, to 1. Three comparisons and we are done.

The code, line by line

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

• lo and hi are the inclusive ends of the current search window. They start as the whole array.
• The loop runs while the window is non-empty (lo <= hi).
• mid = (lo + hi) // 2 is integer division, so it floors to a valid index.
• If a[mid] is too small, the answer is to the right, so we set lo = mid + 1. If it is too big, the answer is to the left, so we set hi = mid - 1. We always move past mid, which is what guarantees the loop ends.
• If the window empties out, the value is not present and we return -1.

Complexity

Why O(log n)? Each comparison cuts the search space in half. You can only halve n about log₂(n) times before you reach a single element — that is roughly 20 steps for a million items, 30 for a billion. The space is O(1) because we only track three indices, no matter how big the array is.

When to use / pitfalls

Practice