Binary Search

Halve a sorted array each comparison to search in logarithmic time.

The idea

Binary search finds a target value in a sorted array — returning the position where it sits, or reporting that it is absent — using about $\log_{2} n$ comparisons on an array of $n$ items.

The saving comes from how much one comparison can rule out. In an unsorted array, a comparison settles a single entry, so a search may need all $n$ of them. In a sorted array, compare the target with the middle entry. If the middle entry is smaller than the target, then so is every entry to its left, because the entries are in order, and the comparison eliminates the whole left half at once. If it is larger, it eliminates the right half instead. If it is equal, the search is over.

Algorithm.

Algorithm: Binary Search Input: sorted array A[0, ..., n-1], target T Output: an index with A[index] = T, or NULL if absent 1. lo = 0, hi = n-1 // if T is present, its index is in [lo, hi] 2. if lo > hi, return NULL // empty range: T is absent 3. mid = ⌊(lo + hi)/2⌋ 4. if A[mid] = T, return mid if A[mid] < T, lo = mid + 1 // A[mid] and everything left of it too small if A[mid] > T, hi = mid - 1 // A[mid] and everything right of it too big 5. go to step 2

Halving a range of $n$ entries down to a single one takes $\log_{2} n$ steps, so each search costs $O(\log n)$ time. Sorting the data once makes every later search logarithmic instead of linear.

Ways to work on it

• Walkthrough. The halving range, the invariant, and why sortedness is required.
• Practice. Run binary search and report where the target lands.
• Hardest. Derive the worst-case comparison count and its logarithmic scaling.

Not sure where to start? Take the ten-question placement test.