3.3 Бинарный поиск¶

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

Сложность алгоритма: O(log n).

Важно: массив должен быть отсортирован.

1. Линейный поиск¶

Простейший способ найти элемент x в массиве:

for (int i = 0; i < n; i++) {
    if (a[i] == x) {
        // элемент найден
    }
}

В худшем случае проверяются все элементы массива. Сложность: O(n).

Если массив не отсортирован, быстрее искать невозможно.

2. Идея бинарного поиска¶

Пусть массив отсортирован по возрастанию.

Алгоритм:

1. Берем середину текущего диапазона.
2. Если значение равно x — поиск завершен.
3. Если середина больше x — продолжаем поиск в левой половине.
4. Если середина меньше x — продолжаем поиск в правой половине.

Схема работы бинарного поиска¶

flowchart TD
    A([Начало]) --> B[Установить l и r]
    B --> C{l меньше или равно r}
    C -- нет --> H[Элемент не найден]
    C -- да --> D[Вычислить середину]
    D --> E{Значение равно x}
    E -- да --> F[Элемент найден]
    E -- нет --> G{Значение больше x}
    G -- да --> I[Сдвинуть правую границу]
    G -- нет --> J[Сдвинуть левую границу]
    I --> C
    J --> C

Каждый шаг уменьшает диапазон в два раза.

Размеры диапазона будут уменьшаться так:

n -> n/2 -> n/4 -> n/8 -> ... -> 1

Количество шагов не превышает log2(n).

3. Классическая реализация¶

int l = 0;
int r = n - 1;

while (l <= r) {
    int mid = l + (r - l) / 2;

    if (a[mid] == x) {
        // найдено
        break;
    }
    if (a[mid] > x) {
        r = mid - 1;
    } else {
        l = mid + 1;
    }
}

Использование формулы l + (r - l) / 2 безопаснее, чем (l + r) / 2, так как предотвращает переполнение.

Сложность: O(log n).

4. Реализация через уменьшение шага¶

Другой способ реализации основан на постепенном уменьшении шага.

int pos = -1;

for (int step = n; step >= 1; step /= 2) {
    while (pos + step < n && a[pos + step] <= x) {
        pos += step;
    }
}

if (pos >= 0 && a[pos] == x) {
    // найдено
}

Идея та же — на каждом этапе шаг уменьшается в два раза.

Сложность: O(log n).

5. Функции стандартной библиотеки C++¶

В C++ бинарный поиск уже реализован в стандартной библиотеке.

lower_bound¶

Возвращает итератор на первый элемент, который не меньше x.

auto it = lower_bound(a, a + n, x);

Проверка существования элемента:

int pos = lower_bound(a, a + n, x) - a;
if (pos < n && a[pos] == x) {
    // элемент найден
}

upper_bound¶

Возвращает первый элемент, который строго больше x.

auto it = upper_bound(a, a + n, x);

Подсчет количества элементов, равных x¶

auto l = lower_bound(a, a + n, x);
auto r = upper_bound(a, a + n, x);

cout << (r - l) << "\n";

Также можно использовать:

auto range = equal_range(a, a + n, x);
cout << (range.second - range.first) << "\n";

Все операции работают за O(log n).

6. Бинарный поиск по ответу¶

Бинарный поиск можно применять к любой монотонной функции.

Предположим, существует функция ok(x), для которой:

• ok(x) == false при x < k
• ok(x) == true при x >= k

Нужно найти минимальное k.

int x = -1;

for (int step = N; step >= 1; step /= 2) {
    while (!ok(x + step)) {
        x += step;
    }
}

int answer = x + 1;

Количество вызовов функции ok: O(log N).

Если ok работает за O(n), итоговая сложность будет O(n log N).

7. Поиск максимума у сначала возрастающей функции¶

Если функция сначала возрастает, а затем убывает, можно найти точку максимума.

Пусть выполняется:

• f(x) < f(x + 1) при x < k
• f(x) > f(x + 1) при x >= k

Тогда k — индекс максимума.

int x = -1;

for (int step = N; step >= 1; step /= 2) {
    while (f(x + step) < f(x + step + 1)) {
        x += step;
    }
}

int k = x + 1;

Важно, чтобы значения функции не были равны на соседних позициях.

8. Когда применять бинарный поиск¶

Бинарный поиск применим, если:

1. Массив отсортирован.
2. Условие является монотонным (false затем true).
3. Функция сначала возрастает, затем убывает.

Если монотонности нет, бинарный поиск использовать нельзя.

Итоги¶

Линейный поиск: O(n) Бинарный поиск: O(log n)

Требует отсортированных данных или монотонности.

Бинарный поиск — один из важнейших инструментов в алгоритмах и соревновательном программировании.