Binary Search

Halve the search space with every comparison.

The idea

Binary search needs one property: the ability to discard half the remaining candidates after a single comparison. On a sorted array that comes free, since comparing against the middle tells you which half the target cannot be in.

The version most people can write from memory is finding an exact value. The version that shows up in interviews is searching for a boundary — the first element satisfying some condition, the insertion point, the smallest workable answer. Same halving, different exit condition.

That generalisation is the useful one: the array does not have to be the thing you search. If you can ask "is x big enough?" and the answer is monotonic — false, false, false, true, true — you can binary search over the answer space, not the input.

low, high = smallest_possible, largest_possible
while low < high:
    mid = low + (high - low) // 2
    if feasible(mid): high = mid
    else:             low = mid + 1
return low

Walkthrough

Eight elements, three comparisons. Watch low and high close in — each read discards half of what is left.

What it costs

time: O(log n)
space: O(1) iteratively, O(log n) recursively

About 20 steps for a million elements, 30 for a billion. The recursive form costs stack frames the iterative one does not.

When to reach for it

The input is sorted, or can be sorted without losing what you need.
You are asked for a boundary: first, last, smallest that works, largest that fits.
The answer space is numeric and the feasibility test is monotonic — search the answer, not the array.
The input is large enough that O(n) is being ruled out deliberately.

Rather than the obvious alternative

A linear scan

20 steps for a million elements against a million. Worth it whenever the data is already sorted; not worth sorting for a single lookup.

A hash map

O(1) exact lookup, but it cannot answer "the smallest value at least x". Binary search is for order, not membership.

How to spot it

The input is sorted, or can be sorted without losing what you need.
You are asked for a boundary: first, last, smallest that works, largest that fits.
The answer space is numeric and the feasibility test is monotonic.
The input is large enough that O(n) is being ruled out deliberately.

Where it goes wrong

The overflow-prone midpoint

`(low + high) / 2` can overflow in fixed-width integer languages. `low + (high - low) / 2` cannot, and costs nothing.

The wrong loop condition

`while (low <= high)` and `while (low < high)` terminate on different states and suit different problems. Pick one deliberately, then check what the surviving index means.

Not moving the bounds

Setting `low = mid` rather than `mid + 1` can leave the range unchanged and loop forever. Every branch must shrink the range.