Binary search and recursion

Remember the game "guess a number from 1 to 100". A sensible first guess is 50: the answer "higher" or "lower" discards half of the numbers at once. Six more such questions, and the number is found.

std::find cannot do that: it checks the elements one by one, and in a vector of a million numbers it may need a million comparisons. In a sorted vector, one comparison with the middle element discards half of the elements at once. That is how std::binary_search searches: it reports whether a value is in a sorted range.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{2, 5, 8, 13, 21, 34};
    std::cout << std::binary_search(v.begin(), v.end(), 13) << ' '
              << std::binary_search(v.begin(), v.end(), 7) << '\n';  // 1 0
}

Halving at each step

Binary search keeps the bounds of the part of the vector where the value can still be. At first, that is the whole vector. On each step, the value is compared with the middle element of the part. If they are equal, the value is found.

If the middle element is less than the value, so is everything to its left, and the search goes right. If it is greater, the search goes left. When the part becomes empty, the value is not in the vector.

In code, the bounds are two indices. The search steps by index:

1. Start with lo = 0 and hi = v.size(): the part is the elements from index lo to hi - 1.
2. While lo < hi, take the middle index mid = (lo + hi) / 2.
3. If v[mid] equals the value, it is found.
4. If v[mid] is less than the value, discard the left half together with mid: lo = mid + 1.
5. If v[mid] is greater than the value, discard the right half together with mid: hi = mid.
6. When lo == hi, the part is empty: the value is not in the vector.

The middle element in steps 4 and 5 has already been checked, so it does not go into the new part. Otherwise the part may stop shrinking, and the loop never ends.

Each step halves the part, so a million elements need about 20 comparisons, which is O(log n). This works only on a sorted vector. In an unsorted one, the discarded half might have held the value.

Recursion

A task can often be reduced to a smaller task of the same kind. Recursion is a function calling itself from its own body. It is like a set of nesting dolls: you open doll after doll until you reach the smallest one, and then you close them in reverse order. The sum_to function adds the numbers from 1 to n, which is n plus the sum up to n - 1.

#include <iostream>

int sum_to(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(4) << '\n';  // 10
}

Let's see what happens:

1. sum_to(4) calls sum_to(3) and waits for its answer. That one calls sum_to(2), and so on down to sum_to(0): these are the opened dolls.
2. The base case n == 0 is the smallest doll: it returns 0 at once, with no further call.
3. Then the calls finish in reverse order, each adding its n to the result it got: 0 + 1 + 2 + 3 + 4 = 10.

Step through the calls: watch the call frames stack up and come off in reverse order.

This is where the analogy stops: a closed doll does nothing more, while a call that gets its answer still finishes its own work and adds n.

A recursive function needs two parts: a base case and a step that brings every call closer to it. Here the step is n - 1. Binary search can be recursive too: its base case is an empty part, and its step searches one of the halves.

Common mistake

The base case is forgotten:

int sum_to(int n) {
    return n + sum_to(n - 1);  // ✗
}

warning: all paths through this function will call itself [-Winfinite-recursion]

The compiler only warns. Every call makes one more call, and none of them returns a result. Such recursion is undefined behavior: the standard does not say what happens when the memory for calls runs out.

Key points

• Binary search works only on a sorted vector and makes O(log n) comparisons.
• The checked middle element does not go into the new part: lo = mid + 1 or hi = mid.
• A recursive function calls itself, and the calls finish in reverse order.
• Without a base case, recursion never ends.