Binary Search

Binary Search

Binary search finds a target in a sorted array by repeatedly halving the range you still need to look at. Each comparison throws away half of the remaining candidates, so a million elements take only about twenty steps.

How it works

Keep two boundaries, low and high, that bracket the part of the array that might contain the target. Look at the middle element:

• If it equals the target, you are done.
• If it is smaller than the target, the answer must be to the right, so move low past the middle.
• If it is larger, the answer is to the left, so move high before the middle.

Repeat until the boundaries cross. The runtime is logarithmic, far faster than scanning every element.

Watch out

The data must be sorted first. A classic bug is computing the middle in a way that overflows on huge indices, so add the offset to low rather than summing both ends. Decide carefully whether boundaries are inclusive to avoid infinite loops.

Key idea

Sorted order lets each step discard half the data, turning linear search into logarithmic search.