Binary Search

On a sorted array, each probe of the middle cell throws away half of the indices that might still hold the target. One comparison decides which half to keep. Repeat that, and a billion values reduce to thirty probes.

The figure above runs exactly this loop. LO and HI mark the bounds of the live range, MID marks the cell under comparison, and the bracket above the cells shows the current [lo, hi]. The target cell carries a small tick until the probe lands on it. Cells fade as they leave the range. Press play and watch one full search, then read on.

The invariant that does the work

Binary search keeps one promise: if the target is in the array, it sits in the live range [lo, hi]. The promise holds at the start, because the range is the whole array. It holds after every probe, because each discard removes only indices that cannot match. And when the range finally runs empty, the promise turns into a proof: no live index remains, so the target is not in the array.

Sorted order is what makes a discard safe. Everything left of mid is less than or equal to the mid value. Everything right of mid is greater than or equal to it. So when the mid value is smaller than the target, nothing at mid or to its left can match, and that whole half can go.

This is also the precondition. Run the loop on an unsorted array and a discard can drop the half that holds the target. The figure enforces the rule: type an unsorted array and it rejects the input instead of running a broken search. If your data arrives unsorted, sort it once and search it many times. Merge sort is one way to get that order.

How one probe works

Keep two inclusive bounds, lo and hi, starting at 0 and n - 1. While lo <= hi, probe the midpoint:

1. Set mid to the index halfway between lo and hi.

2. If the mid value equals the target, stop. You have an index.

3. If the mid value is smaller than the target, set lo to mid + 1.

4. If the mid value is larger than the target, set hi to mid - 1.

When lo rises past hi, the range is empty. Report a miss.

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

Three details in this loop carry the invariant. The range is inclusive, so the test is lo <= hi. A one-element range still deserves a probe. The updates move past mid, because mid was just compared. Leave mid in the range and a two-cell range can loop forever.

The midpoint is lo + (hi - lo) // 2, not (lo + hi) // 2, because the sum can overflow a fixed-width integer when both bounds are large. The figure uses (lo + hi) >> 1 because its demo arrays stay small. Use the overflow-safe form in production code.

A walkthrough, probe by probe

Take the figure's starting array, [2, 5, 8, 12, 17, 23, 29, 34], with target 23. The live range starts at [0, 7].

1. Probe index 3. The cell holds 12. Because 12 is smaller than 23, nothing at or left of index 3 can match. Set lo to 4. The range becomes [4, 7], and the four discarded cells fade.

2. Probe index 5. The cell holds 23. That is the target. The search ends.

Two probes for eight values, and the left half never gets a second look. The figure below starts from the same array and target. Press play in the above interactive element and it runs exactly these steps.

A miss runs on the same rule. In either figure, type 16 into the target field. Press play. The probes hit 12, then 23, then 17. Each discard is sound, so when the range collapses after the third probe, the collapse itself is the answer: 16 is not in the array.

Then make it yours. Click any cell to search for its value, or type a sorted array of up to ten numbers with a new target. The walk restarts, and the invariant holds every time.

Why the probe count is logarithmic

Each probe cuts the live range to at most half its previous length. After k probes, at most n / 2^k cells remain. The loop ends when that count drops below one, which happens after about log2 n probes. Where the target sits changes which probes run and whether the loop stops early. A first-probe hit is the best case. A miss, or a target hiding in a corner, runs the full count.

The worst case grows slowly:

Space stays flat. The iterative loop stores three integers, so extra space is O(1). A recursive version pays O(log n) stack frames instead, one per probe.

This is why sorted data is such a strong asset. Sorting costs O(n log n) once, and every lookup after that costs almost nothing. Linear search asks nothing up front and pays O(n) on every lookup.

The same trick without an array

Binary search needs two things: a range of candidate answers and a question with a monotonic answer. Monotonic means every no sits left of every yes: once the answer flips to yes, it never flips back. Ask the question at the midpoint and each probe still discards half. The array is the special case where the candidates are indices and the question is “is the mid value smaller than the target?”

The pattern pays off wherever testing a candidate is cheaper than listing every candidate:

• First bad version: find the earliest commit where the tests start to fail.

• Capacity: find the smallest ship capacity that still moves every package on time.

• Roots: find the largest integer whose square does not exceed n.

Duplicates need one change. A hit on 23 in [17, 23, 23, 23, 29] can land on any of the three copies. To find the first copy, record the hit and keep searching left: set hi to mid - 1. That variant is the lower bound: the first index whose value is at least the target. It ships next to the classic loop in the implementation panel on this page.

When to reach for it

Reach for binary search when three things hold:

• The data is sorted, or you can sort it once and search many times.

• You can read any index in constant time. Arrays qualify. Linked lists do not, because reaching the middle means walking half the list.

• Lookups dominate the work. If every query needs a full pass over the data anyway, sorting buys nothing.

Skip it for a single search through unsorted data. Sorting first costs O(n log n), and one linear scan costs O(n). The prepayment pays off only across many lookups.

The practice problems below all reduce to one idea: probe the middle, discard the half that cannot match, and trust the invariant. Start with an easy one and watch for the moment the problem tells you which half to keep.