Алгоритмы

Введение в алгоритмы двоичного поиска

Двоичный поиск (Binary Search) — это один из фундаментальных алгоритмов в программировании, который позволяет находить элемент в отсортированном массиве или списке за логарифмическое время O(log n). В отличие от линейного поиска, где мы проверяем каждый элемент по порядку, двоичный поиск на каждой итерации отсекает половину оставшегося пространства поиска.

Однако в реальной разработке и спортивном программировании «чистый» двоичный поиск — это лишь верхушка айсберга. На практике мы гораздо чаще сталкиваемся с его вариациями, такими как lower_bound и upper_bound, а также с мощнейшим методом — поиском по ответу (Binary Search on Answer). В этой статье мы разберем эти техники подробно.

Различие между lower_bound и upper_bound

Когда мы работаем с массивом, содержащим дубликаты или когда нам нужно найти позицию для вставки элемента, обычного двоичного поиска недостаточно. Здесь на сцену выходят две классические вариации:

lower_bound: возвращает индекс первого элемента, который больше или равен искомому значению (x).
upper_bound: возвращает индекс первого элемента, который строго больше искомого значения (x).

Разница между ними критически важна при подсчете количества вхождений числа или поиске границ диапазона. Например, если массив содержит [1, 2, 4, 4, 4, 5] и мы ищем число 4:

lower_bound укажет на индекс 2 (первая четверка).
upper_bound укажет на индекс 5 (число 5).

Разница между этими индексами даст нам точное количество повторений числа в массиве. Ниже приведен пример реализации этих функций на языке C++ (логика аналогична для других языков):


// Находит первый индекс элемента >= target
int lower_bound(const std::vector& arr, int target) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Находит первый индекс элемента > target
int upper_bound(const std::vector& arr, int target) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] > target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

Поиск по ответу: когда массив — это не просто массив

Самая интересная вариация двоичного поиска — поиск по ответу. Этот метод применяется, когда мы не ищем число в готовом массиве, а пытаемся найти оптимальное значение в некоем диапазоне, удовлетворяющее заданному условию.

Главное условие для применения этого метода — монотонность. Если функция f(x) такова, что при увеличении x результат функции меняется только в одну сторону (например, с "ложного" на "истинный"), мы можем использовать двоичный поиск.

Типичная структура задачи:

Определить границы диапазона ответов (например, от 1 до 10⁹).
Написать функцию check(x), которая проверяет, возможноно ли достичь цели при значении x.
Применить двоичный поиск для поиска минимального или максимального x, при котором check(x) истинно.

Реальный пример: Найдите минимальное время, за которое грузовик сможет перевезти все грузы из пункта А в пункт Б, если он может перевозить не более W тонн за раз и делает остановки на заправку.


// Пример логики поиска по ответу (псевдокод)
bool can_deliver(int time, int weight_limit) {
    // Логика симуляции процесса перевозки за заданное время
    return true; // или false
}

int solve() {
    int low = 0, high = 1e9; // Диапазон возможных минут
    int ans = high;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (can_deliver(mid, weight_limit)) {
            ans = mid;      // Запасной вариант работает, пробуем найти меньшее время
            high = mid - 1;
        } else {
            low = mid + 1;  // Время недостаточно, увеличиваем интервал
        }
    }
    return ans;
}

Практические рекомендации и нюансы

При реализации двоичного поиска важно учитывать несколько технических моментов, которые часто приводят к ошибкам в продакшене:

Переполнение при расчете середины: Вместо (low + high) / 2 всегда используйте low + (high - low) / 2. Это предотвращает переполнение типа данных, если low и high очень велики.
Границы цикла: Будьте внимательны к условию `while (low < high)` или `while (low <= high)`. При использовании lower_bound логика обычно строится на «полуоткрытом» интервале, где high — это первый элемент, который точно не подходит.
Тип данных: Если вы ищете ответ в очень большом диапазоне (например, количество комбинаций), используйте 64-битные целые числа (long long в C++, int или long в Python/Java).
Оптимизация условия: В задачах на поиск по ответу, если вам нужно найти минимальное значение, которое удовлетворяет условию, и функция "переключается" с false на true один раз, двоичный поиск — самый эффективный способ.

`Подведение итогов`

Двоичный поиск — это не просто алгоритм поиска элемента в списке. Это мощный инструмент решения задач оптимизации. lower_bound и upper_bound позволяют эффективно работать с диапазонами и дубликатами, а поиск по ответу превращает сложные задачи на поиск минимума/максимума в простые проверки условий. Освоив эти три гранюса алгоритма, вы сможете решать широкий спектр задач от системного программирования до сложных вычислительных задач.

Введение в алгоритмы двоичного поиска