Searching: linear and binary

Linear search

int linear_search(const int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;
    return -1;
}

O(n), works on any data in any order, and for small arrays it is genuinely the right answer. Do not dismiss it - it needs no sorting, no preprocessing, and it is impossible to get wrong.

Binary search

Requires the array to be sorted. Each step throws away half the range.

#include <iostream>
using namespace std;

int binary_search_index(const 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;
        else if (a[mid] < key)  lo = mid + 1;
        else                    hi = mid - 1;
    }
    return -1;
}

int main() {
    int a[] = {11, 22, 33, 44, 55, 66, 77};
    int n = 7;
    cout << binary_search_index(a, n, 55) << "\n";   // 4
    cout << binary_search_index(a, n, 11) << "\n";   // 0
    cout << binary_search_index(a, n, 50) << "\n";   // -1
    return 0;
}

Nine lines. Every one of them is a place people get it wrong. Take them one at a time.

Bug 1: the loop condition

It must be lo <= hi, not lo < hi.

With lo < hi, the loop stops when lo == hi - a range with exactly one element left, which never gets checked. Search for 11 in the array above and you get -1 even though it is at index 0.

To convince yourself: search a 1-element array. lo = 0, hi = 0. With lo < hi the loop body never runs at all.

Bug 2: computing mid

The obvious version is int mid = (lo + hi) / 2;. It is wrong, and the bug survived in the Java standard library for nine years before anyone noticed.

If lo and hi are both large, lo + hi overflows a 32-bit int. The maximum is 2,147,483,647; two indices near 1.5 billion sum past it and the result goes negative. a[negative] is undefined behaviour.

int mid = lo + (hi - lo) / 2;   // correct: hi - lo cannot overflow

hi - lo is at most the array size, so it is always safe. Write it this way every time, out of habit.

Tracing it

Search for 66 in {11, 22, 33, 44, 55, 66, 77}.

Search for 50:

Step 3 is the one lo < hi would have skipped.

Why it is O(log n)

Start with n elements. After one step: n/2. After two: n/4. After k steps: n / 2^k. The search ends when that reaches 1, so 2^k = n, so k = log2(n).

For n = 1,000,000, that is 20 steps. A linear search would average 500,000.

Finding the first occurrence

Plain binary search returns some index holding the key. With duplicates, you often need the first one. This variant is the standard follow-up question.

int lower_bound_index(const int a[], int n, int key) {
    int lo = 0, hi = n;            // note: hi = n, not n - 1
    while (lo < hi) {              // note: strict <
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else              hi = mid;
    }
    return lo;   // first index with a[i] >= key; n if there is none
}

int main() {
    int a[] = {1, 2, 2, 2, 5, 9};
    cout << lower_bound_index(a, 6, 2) << "\n";   // 1
    cout << lower_bound_index(a, 6, 3) << "\n";   // 4
    cout << lower_bound_index(a, 6, 9) << "\n";   // 5
    return 0;
}

This is the other consistent pair: hi = n, lo < hi, hi = mid. The range is half-open [lo, hi), which is why hi starts one past the end. Never has an infinite loop, never misses an element. It is what C++'s std::lower_bound does.

When binary search does not apply

• The array is not sorted. Sorting costs O(n log n), so for a single lookup

linear search is cheaper.

• The data is a linked list. Jumping to the middle is O(n), which destroys

the benefit.

• You will search only once or twice. Sort plus search is O(n log n); one

linear scan is O(n).