Binary search and recursion

std::find 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.

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. 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
}

The call sum_to(4) calls sum_to(3), which calls sum_to(2), and so on down to sum_to(0). The base case n == 0 returns its answer at once, with no further call. Then the calls finish in reverse order, each adding its n to the result it got: 0 + 1 + 2 + 3 + 4 = 10.

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.