Binary Search

Binary search finds a value in a sorted list by halving the search space on every comparison. It's simple to describe and easy to implement wrongly. The fix is one invariant, below.

The Problem

Given a sorted list and a target, return the target's index, or -1 if it's absent.

Sortedness is what makes this fast. One comparison against the middle element rules out half the list: if the middle is smaller than the target, so is everything to its left.

The Idea

Track a search window, the range that might still contain the target, using two positions: low and high. Start with the whole list, then repeat:

1. Probe. Look at the middle element of the window.
2. Match? Done, return its index.
3. Too small? The target is to the right. Move low just past the middle.
4. Too big? The target is to the left. Move high just before the middle.

Empty window means the target isn't in the list.

Correctness rests on one invariant:

True at the start (the window is the whole list). True after every step (only elements proven too small or too big get discarded). So when the window empties, the target can't be anywhere: return -1.

Step Through It

The greyed-out cells are ruled out; the window is what's left. Try a target that isn't in the array.

Why It's Fast

Each step halves the window. Halving 12 elements down to 1 takes about 4 steps. A million takes 20. A billion takes 30. That count of halvings is what $O(\log n)$ means: the work grows by one step each time the input doubles.

No comparison-based search of a sorted list can do better.

Implementation

The window is a[low..high], inclusive at both ends. Every update is one of the moves from the list above:

def binary_search(a: list[int], target: int) -> int:
    low, high = 0, len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

func binarySearch(a []int, target int) int {
	low, high := 0, len(a)-1
	for low <= high {
		mid := low + (high-low)/2
		if a[mid] == target {
			return mid
		} else if a[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

function binarySearch(a: number[], target: number): number {
  let low = 0;
  let high = a.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (a[mid] === target) {
      return mid;
    } else if (a[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Two pitfalls:

Overflow. Python's integers can't overflow, so (low + high) // 2 is safe here. In fixed-width languages the sum can overflow on huge arrays; this bug hid in Java's standard library for nearly a decade. The safe form:

mid = low + (high - low) // 2

Off-by-one errors. Don't guess at the + 1s and - 1s. Check each line that moves low or high against the invariant: could it discard a cell that might still hold the target? If no line can, the search is correct.

Wrapping Up

Keep a window that must contain the target if it exists; halve it with every comparison. The same pattern powers guessing games, git bisect, and Python's bisect_left/bisect_right.