Binary search

Introduction

Linear search checks items one by one: O(n). If the array is sorted, binary search does much better: compare the key with the middle item, and throw away the half that cannot contain it. Each comparison halves the range, so it needs at most about log₂ n + 1 comparisons: 20 for a million items.

Searching is the question programs ask most. Sorting the data once and using binary search turns a walk through a million items into about twenty comparisons, and a small change to the same loop answers harder questions too.

How it works

Binary search

#include <stdio.h>

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

int main(void) {
    int a[] = {3, 8, 15, 21, 30, 42, 57, 64, 70, 88};
    printf("42 is at index %d\n", binary_search(a, 10, 42));
    printf("50 is at index %d\n", binary_search(a, 10, 50));
    return 0;
}

The search keeps a range lo .. hi that must contain the key, if it is there at all:

• a[mid] == key: found;
• a[mid] < key: the key can only be to the right, so lo = mid + 1;
• a[mid] > key: only to the left, so hi = mid - 1.

When lo > hi the range is empty, and the key is missing. Watch lo, mid and hi close in. mid = lo + (hi - lo) / 2 gives the same answer as (lo + hi) / 2, but cannot overflow when lo and hi are near the largest int.

Syntax

int mid = lo + (hi - lo) / 2;      // cannot overflow, unlike (lo + hi) / 2

// closed range lo .. hi, loop while lo <= hi
if (a[mid] < key) lo = mid + 1; else hi = mid - 1;

// half-open range lo .. hi-1, loop while lo < hi
if (a[mid] < key) lo = mid + 1; else hi = mid;

Example

#include <stdio.h>

int lower_bound(int a[], int n, int key) {   // the first index with a[i] >= key
    int lo = 0, hi = n;                       // the answer is somewhere in lo .. hi
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main(void) {
    int a[] = {1, 2, 2, 2, 5, 7};
    int n = 6;
    printf("first 2 at index %d\n", lower_bound(a, n, 2));
    printf("number of 2s: %d\n", lower_bound(a, n, 3) - lower_bound(a, n, 2));
    printf("6 would go at index %d\n", lower_bound(a, n, 6));
    return 0;
}

With duplicates, plain binary search finds some copy of the key. lower_bound finds the first index whose value is at least the key. Its range is lo .. hi with hi one past the end, and it never stops early: when a[mid] >= key, the answer is mid or something to its left, so hi = mid.

The same function answers three questions:

• where the first 2 is: lower_bound(a, n, 2);
• how many 2s there are: lower_bound(a, n, 3) - lower_bound(a, n, 2);
• where to insert 6 to keep the array sorted: lower_bound(a, n, 6).

Binary search can also be written recursively: search the left or right half by calling the function again with a smaller range.

Line by line

1. lower_bound starts with lo = 0 and hi = n, because the answer may be n when every item is smaller than the key.
2. The loop runs while lo < hi, which means while there is more than one possible answer.
3. mid is the middle of the range. It is always less than hi, so a[mid] is a real item.
4. If a[mid] is smaller than the key, then mid and everything before it are too small, so lo = mid + 1.
5. Otherwise mid might be the answer, or something to its left might be, so hi = mid keeps it in the range.
6. When lo equals hi, one candidate is left, and that is the result.
7. main asks the three questions: the first 2 is at index 1, there are 4 - 1 = 3 copies, and 6 would go at index 5.

Expected result

first 2 at index 1
number of 2s: 3
6 would go at index 5

In the real world

A database index uses the same idea to find a row among millions, and a version-control tool such as git bisect halves a list of commits to find the one that introduced a bug. Library functions like C's bsearch and C++'s lower_bound are built on this loop.

Common mistakes

• Binary search on an unsorted array: it gives wrong answers without any error.
• while (lo < hi) with hi = mid - 1, or while (lo <= hi) with hi = mid: mixing the two styles loses an item or loops forever. Pick one style and keep its rules.
• Writing mid = (lo + hi) / 2 when the indexes can be very large, which can overflow.

Best practices

• Write down what lo and hi mean before writing the loop.
• Test with one item, with the key at each end, and with a missing key.
• Use the library function in real programs, and know what it promises.

Summary

Binary search halves a sorted range on every comparison, so it takes O(log n) steps. Keeping a clear invariant makes it correct, and lower_bound extends it to duplicates, counts and insertion points.

Mark lesson complete