Binary Search

Idea

Binary Search halves the search range each step—requires a sorted list.

When to use

• Sorted linear list (array or list)
• Large data, frequent queries

Algorithm

1. Range $[low, high]$
2. $mid = \lfloor (low + high) / 2 \rfloor$
3. If $A[mid] = x$, success
4. If $A[mid] < x$, search right half
5. If $A[mid] > x$, search left half
6. Stop when $low > high$

Pseudo-code:

low = 0, high = n-1
while low <= high:
    mid = (low + high) // 2
    if A[mid] == x:
        return mid
    elif A[mid] < x:
        low = mid + 1
    else:
        high = mid - 1
return -1

Implementation

// Binary search, recursive form. Requires A[0..n-1] to be sorted ascending.
int BinarySearch(int A[], int low, int high, int key) {
    if (low > high) return -1;            // not found
    int mid = (low + high) / 2;
    if (A[mid] == key) return mid;        // found
    else if (A[mid] < key)
        return BinarySearch(A, mid + 1, high);  // keep the right half
    else
        return BinarySearch(A, low, mid - 1);   // keep the left half
}

The recursive form is the clearest way to state the algorithm, but it is not the fastest: every level of recursion costs a stack frame. In production the iterative form shown in the pseudo-code above is preferred, because it keeps the two bounds in registers and touches memory only when it actually reads an element.

The decision tree and the average search length

The whole search process can be drawn as a decision tree: every node is one comparison against the midpoint mid of the current range.

• The decision tree is a balanced binary tree (or close to it), with one node per element, so it has $n$ nodes.
• The longest successful search takes as many comparisons as the height of the tree, $\lceil \log_2(n+1) \rceil$.
• The average search length is approximately $ASL \approx \log_2(n+1) - 1$.

Take $n = 11$ as an example. The tree has height $\lceil \log_2 12 \rceil = 4$, and the level sizes are $1, 2, 4, 4$, so

$$ASL = \frac{1\times1 + 2\times2 + 3\times4 + 4\times4}{11} = \frac{1+4+12+16}{11} = \frac{33}{11} = 3$$

That is, a successful search takes 3 comparisons on average.

The point of the tree is that it explains why the average is close to the worst case. Because the tree is balanced, almost every element sits on one of the lower levels, so the average number of comparisons is close to the height — the algorithm is not merely fast in the worst case, it is fast on average too. It also makes the cost model independent of the data distribution, unlike linear search, whose cost depends on where the target happens to sit.

Variants of binary search

In practice you often need a boundary rather than an element — the first position of a value, or the first position at which a value would be inserted. These “binary search variants” are a frequent interview topic:

The implementation trick is the same in all four: on a hit, do not return — keep shrinking the range in one direction instead. The left-boundary search keeps moving high down; the right-boundary search keeps moving low up. The loop then ends with the boundary sitting in the variable you tracked, whether or not an exact match ever occurred.

// First index with A[i] >= key, or n if there is none.
int LowerBound(int A[], int n, int key) {
    int low = 0, high = n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (A[mid] < key) low = mid + 1;
        else high = mid;
    }
    return low;
}

Note the half-open range [low, high) and the low < high loop condition: this shape returns n when no element qualifies, so the caller never needs a special case for “not found”.

Complexity

• Best: $O(1)$
• Worst/avg: $O(\log_2 n)$

Exercises

Exercise 1

For sorted $A = [1, 3, 5, 7, 9, 11]$, find $7$.

Exercise 2

What are the applicable conditions of binary search, and what is its time complexity?

Past exam

2017·408

What is the search process of binary search, and how efficient is it?