Step 2 of 6

Binary search

Looking for a word in a dictionary, you don't start at page 1. You open the middle, see whether your word comes before or after, and throw away the half it can't be in. After about 20 halvings, a million pages are down to one. That's binary search, and it only works on sorted data.

lo = 0, hi = n - 1
while lo <= hi:
    mid = lo + (hi - lo) / 2      (not (lo + hi) / 2: that can overflow!)
    if v[mid] == target: found
    if v[mid] < target: lo = mid + 1
    else: hi = mid - 1

Here it is on a sorted list of words, printing each step so you can watch the range shrink:

#include <iostream>
#include <string>
#include <vector>

int find_word(const std::vector<std::string>& words, const std::string& target) {
    int lo = 0, hi = (int)words.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        std::cout << "  look at [" << lo << ", " << hi << "] middle " << words[mid] << "\n";
        if (words[mid] == target) return mid;
        if (words[mid] < target) lo = mid + 1;    // target is to the right
        else hi = mid - 1;                        // target is to the left
    }
    return -1;
}

int main() {
    std::vector<std::string> w = {"ant", "bee", "cat", "dog", "eel", "fox", "gnu", "hen"};
    int fox = find_word(w, "fox");
    std::cout << "fox at " << fox << "\n";
    int cow = find_word(w, "cow");
    std::cout << "cow at " << cow << "\n";
}

  look at [0, 7] middle dog
  look at [4, 7] middle fox
fox at 5
  look at [0, 7] middle dog
  look at [0, 2] middle bee
  look at [2, 2] middle cat
cow at -1

Why it's fast

Each step halves the range: 8, 4, 2, 1. A million elements need at most 20 steps, a billion about 30. That's O(log n).

The details that matter

• lo <= hi, not lo < hi: when lo == hi there's still one element left to check.
• lo = mid + 1 and hi = mid - 1: mid was already checked, so exclude it. Writing lo = mid can loop forever when hi == lo + 1.
• lo + (hi - lo) / 2 instead of (lo + hi) / 2: for huge arrays, lo + hi can overflow an int. This exact bug sat in Java's standard library for about nine years.
• When the loop ends without finding it, lo > hi and the target isn't there. Also note lo is where the target would be inserted, which is the idea behind lower_bound in the next step.

Binary search is famously easy to get subtly wrong. Write it carefully once and understand every + 1 and - 1.

Your task

Write int find_index(const std::vector<int>& v, int target) returning the index of target in the sorted vector v, or -1. Don't use the standard library's search functions.

Challenge 2

Write int first_at_least(const std::vector<int>& v, int target) for a sorted v: the index of the first element >= target, or v.size() if there's none. This is std::lower_bound, written by hand: keep a half-open range [lo, hi) and halve it.

Challenge 3

Binary search also works on answers. Write long long isqrt(long long n), the largest x with x * x <= n, for 0 <= n <= 10^18, by binary searching on x. Don't use sqrt (floating point is not exact at this size), and watch out for overflow in x * x.

Previous: Big-O in practice Next: lower_bound and upper_bound