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

Вспомните игру «угадай число от 1 до 100». Первым ходом разумно назвать 50: ответ «больше» или «меньше» сразу отбрасывает половину чисел. Ещё шесть таких вопросов — и число угадано.

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
}

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

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

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

В коде границы — это два индекса. Шаги поиска по индексам:

1. Начните с lo = 0 и hi = v.size(): часть — элементы с индекса lo по hi - 1.
2. Пока lo < hi, возьмите средний индекс mid = (lo + hi) / 2.
3. Если v[mid] равен значению, оно найдено.
4. Если v[mid] меньше значения, отбросьте левую половину вместе с mid: lo = mid + 1.
5. Если v[mid] больше значения, отбросьте правую половину вместе с mid: hi = mid.
6. Когда lo == hi, часть пустая: значения в векторе нет.

Средний элемент в шагах 4 и 5 уже проверен, поэтому он не попадает в новую часть. Иначе часть может перестать уменьшаться, и цикл не закончится.

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

Рекурсия

Задачу часто можно свести к меньшей задаче того же вида. Рекурсия — вызов функции из её собственного тела. Она похожа на матрёшку: вы открываете куклу за куклой, пока не дойдёте до самой маленькой, а потом закрываете их в обратном порядке. Функция 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
}

Давайте разберём, что происходит:

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

Пройдите вызовы по шагам: следите, как рамки вызовов ложатся друг на друга и снимаются в обратном порядке.

Здесь аналогия заканчивается: закрытая матрёшка больше ничего не делает, а вызов, получив ответ, ещё доделывает свою работу — прибавляет n.

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

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

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

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

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

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

Главное

• Бинарный поиск работает только на отсортированном векторе и делает O(log n) сравнений.
• Проверенный средний элемент не попадает в новую часть: lo = mid + 1 или hi = mid.
• Рекурсивная функция вызывает себя, и вызовы завершаются в обратном порядке.
• Без базового случая рекурсия не заканчивается.