Binary search

Guess a number from 1 to 100, told only “higher” or “lower”: start at 50 and every answer halves what is left. Watch the same trick find 100 among 64 sorted numbers.

⋯9static int probes = 0;10 11int binary_search(const int *a, int n, int key)12{13    int lo = 0, hi = n - 1;14    while (lo <= hi) {15        int mid = lo + (hi - lo) / 2;16        probes++;17        if (a[mid] == key)18            return mid;19        if (a[mid] < key)20            lo = mid + 1;21        else22            hi = mid - 1;23    }24    return -1;25}⋯27int main(void)28{29    int a[N];30    for (int i = 0; i < N; i++)31        a[i] = 3 * i + 1;32    int at = binary_search(a, N, KEY);33    printf("key %d: index %d after %d probes\n", KEY, at, probes);34    return 0;35}

Halving what is left

A linear search can rule out only one cell per comparison. If the array is sorted, one comparison with the middle cell rules out half the array: if the middle is smaller than the key, the key can only be to its right; if larger, only to its left. Each probe halves what is left, so even a million cells take only about 20 probes.

This only works because the array is in order. In an unsorted array, a smaller middle says nothing about which half the key is in.

The code and its cost

The loop

int binary_search(const int *a, int n, int key)
{
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        probes++;
        if (a[mid] == key)
            return mid;
        if (a[mid] < key)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

lo and hi are the first and last cells still in the running; mid is the cell halfway between. After a probe the range shrinks to one side of mid, and mid itself is left out, since it has just been checked.

The invariant

The loop keeps one promise, its invariant: if the key is in the array, it lies in a[lo..hi]. It is true at the start, when lo..hi is the whole array, and each probe keeps it true, because the half it drops cannot hold the key. When the range is empty, lo > hi, the key cannot be anywhere, and the function returns -1. The loop always ends: every pass makes the range at least one cell shorter.

How many probes

Each probe either finds the key or leaves at most half the range. A range of n cells can be halved ⌊log₂ n⌋ times before one cell is left, and that last cell takes one more probe, so a search takes at most

probes, found or not: 7 for 64 cells, 20 for a million, 30 for a billion.

Writing mid

(lo + hi) / 2 looks simpler, but lo + hi can pass the largest int, 2,147,483,647, on a very large array, and signed overflow in C is undefined. lo + (hi - lo) / 2 never adds two large numbers: hi − lo is at most the length of the range.

Worked example

Key 100, by hand.

Key 101, absent. The first five probes are the same, until (32, 34, 33): 100 < 101, so lo = 34. Then (34, 34, 34): a[34] = 103 > 101, so hi = 33. Now lo is past hi and the search stops after 6 probes with -1. The ends: 190, the last cell, takes 7 probes, at cells 31, 47, 55, 59, 61, 62 and 63; 0, below every cell, takes 6, at 31, 15, 7, 3, 1 and 0, and stops with hi = −1.

Two off-by-one mistakes. Starting with hi = n while the loop tests lo <= hi lets mid reach n, one past the last cell. bsearch-hi-n.c searches 1 4 7 10 13 16 for 20 that way; the sanitiser build stops with stack-buffer-overflow, a read of 4 bytes past the array in binary_search. Reading past the array is undefined behaviour; this plain build read whatever lay there, went on and printed -1.

Writing lo = mid instead of lo = mid + 1 can stop the range from shrinking. In bsearch-lo-mid.c, looking for 16, the last of the six, the range reaches lo = 4, hi = 5; mid is 4 + (5 − 4)/2 = 4, a[4] = 13 is smaller than 16, and lo = mid leaves lo at 4. The same pass repeats for ever; the program stops itself after 6 passes, printing passes 4, 5 and 6 each as lo 4, hi 5, mid 4.

Overflow. With lo = 1,500,000,000 and hi = 1,600,000,000, lo + hi = 3,100,000,000, more than 2,147,483,647. lo + (hi - lo) / 2 gives 1,550,000,000 without ever leaving the range of int. overflow-mid.c prints both.

Recursively. The same search can call itself on the half that is left, one call per probe:

int search(const int *a, int lo, int hi, int key)
{
    if (lo > hi)
        return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == key)
        return mid;
    if (a[mid] < key)
        return search(a, mid + 1, hi, key);
    return search(a, lo, mid - 1, key);
}

On the 64 cells it goes 5 calls deep for 100 and 7 for 190, never more than the loop’s probes. (The traced recursive.c writes the same function with a depth counter added.)

Two checks. At most how many probes for 1,000 items? (⌊log₂ 1000⌋ + 1 = 10.) Why must the array be sorted? (Otherwise comparing with the middle cannot rule out a half.)

Where it’s used

Sorted tables. Dictionaries, symbol tables and indexes kept in order are searched this way; the C library’s bsearch does it for any array and comparison function.

Finding a bad change. Version-control tools bisect a history of changes: test the middle one, and half the history is cleared at each step.

Solving equations. Finding where a function crosses zero by halving an interval that contains the crossing is the same idea on numbers instead of cells.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.