Бинарный поиск и рекурсия

std::find проверяет элементы по очереди, и в векторе из миллиона чисел ему может понадобиться миллион сравнений. В отсортированном векторе одно сравнение со средним элементом отбрасывает сразу половину. Так ищет std::binary_search: он сообщает, есть ли значение в отсортированном диапазоне.

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

Половина за шаг

Бинарный поиск (binary search) помнит границы части вектора, где значение ещё может быть. Сначала это весь вектор. На каждом шаге значение сравнивают со средним элементом части, и если они равны, значение найдено.

Если средний элемент меньше значения, то и все элементы левее него меньше, поэтому искать дальше нужно справа. Если больше — слева. Когда часть становится пустой, значения в векторе нет.

Каждый шаг уменьшает часть вдвое, поэтому миллиону элементов хватает около 20 сравнений — это O(log n). Работает это только на отсортированном векторе. В неотсортированном отброшенная половина могла содержать искомое значение.

Рекурсия

Задачу часто можно свести к меньшей задаче того же вида. Рекурсия (recursion) — вызов функции из её собственного тела. Функция sum_to складывает числа от 1 до n: это n плюс сумма чисел до 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
}

Вызов sum_to(4) вызывает sum_to(3), тот — sum_to(2), и так до sum_to(0). Базовый случай (base case) n == 0 возвращает ответ сразу, без нового вызова. Затем вызовы завершаются в обратном порядке, и каждый прибавляет своё n к полученному результату: 0 + 1 + 2 + 3 + 4 = 10.

Рекурсивной функции нужны две части: базовый случай и шаг, который приближает к нему каждый вызов. Здесь шаг — n - 1. Бинарный поиск тоже можно записать рекурсивно: базовый случай — пустая часть, а шаг — поиск в одной из половин.

Частая ошибка

Базовый случай забывают:

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

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

Компилятор (compiler) только предупреждает. Каждый вызов делает ещё один, и ни один из них не возвращает результат. Такая рекурсия — неопределённое поведение: стандарт не говорит, что случится, когда закончится память для вызовов.