Поиск: бинарный поиск и его вариации, std::lower_bound/upper_bound

Введение

Бинарный поиск как принцип, лежащий в основе поиска в сбалансированном дереве — в этой статье разберём бинарный поиск отдельно, как самостоятельный алгоритм для отсортированных линейных коллекций, и его практичные вариации через std::lower_bound/upper_bound/binary_search.

Концепция

Бинарный поиск работает только на отсортированной коллекции, последовательно сужая диапазон поиска вдвое на каждом шаге — сравнивая искомое значение со средним элементом текущего диапазона и отбрасывая половину диапазона, заведомо не содержащую искомое значение (благодаря отсортированности), что даёт O(log n) сложность вместо O(n) у линейного поиска. std::lower_bound находит первую позицию, куда можно вставить искомое значение, не нарушая отсортированность (первый элемент, не меньший искомого значения), std::upper_bound — первую позицию строго после всех элементов, равных искомому значению, а разница между ними (std::equal_range) даёт весь диапазон элементов, равных искомому значению, что особенно полезно при наличии дубликатов в коллекции.

Пример кода

// std::binary_search — простая проверка наличия элемента в отсортированной коллекции
std::vector<int> sortedData = {1, 3, 5, 7, 9, 11, 13};
bool found = std::binary_search(sortedData.begin(), sortedData.end(), 7); // true, O(log n)

// lower_bound/upper_bound — поиск диапазона элементов с заданным значением (учитывая дубликаты)
std::vector<int> withDuplicates = {1, 3, 3, 3, 5, 7, 9};

auto low = std::lower_bound(withDuplicates.begin(), withDuplicates.end(), 3); // первая позиция значения 3
auto up = std::upper_bound(withDuplicates.begin(), withDuplicates.end(), 3);  // позиция ПОСЛЕ последней 3

qDebug() << "Количество элементов со значением 3:" << std::distance(low, up); // 3

// Практическое применение — поиск позиции вставки для сохранения отсортированности
std::vector<int> sortedScores = {10, 25, 40, 55, 70, 90};
int newScore = 48;

auto insertPos = std::lower_bound(sortedScores.begin(), sortedScores.end(), newScore);
sortedScores.insert(insertPos, newScore); // вставка с сохранением отсортированности — O(log n) поиск + O(n) сдвиг
// {10, 25, 40, 48, 55, 70, 90}

Пояснения к коду

std::binary_search даёт только булев ответ (присутствует элемент или нет), не указывая его конкретную позицию — для случаев, когда нужна именно позиция, используются lower_bound/upper_bound, дополнительно работающие корректно и для отсутствующего значения (возвращая позицию, куда оно могло бы быть вставлено). Разница std::distance(low, up) для коллекции с дубликатами демонстрирует практичный способ подсчёта количества элементов с конкретным значением без полного линейного перебора коллекции — оба вызова lower_bound/upper_bound выполняются за O(log n), что для большой коллекции с многочисленными дубликатами значительно эффективнее наивного подсчёта через полный перебор. Поиск позиции вставки через lower_bound с последующим insert показывает практичный, идиоматичный паттерн поддержания отсортированности коллекции при добавлении новых элементов — хотя сама вставка в vector остаётся O(n) (сдвиг последующих элементов), нахождение корректной позиции для этой вставки выполняется значительно быстрее линейного перебора.

Подводные камни

• Применение бинарного поиска (или его вариаций) к неотсортированной коллекции — алгоритм фундаментально полагается на отсортированность для корректности логики «отсечения половины диапазона», и применение к неотсортированным данным даёт неопределённый, формально некорректный результат без какой-либо автоматической проверки или предупреждения об этом нарушенном предположении — ответственность за обеспечение отсортированности коллекции перед использованием бинарного поиска лежит полностью на разработчике.
• Повторное использование бинарного поиска для коллекции, часто изменяющейся между поисками, без учёта стоимости поддержания отсортированности при каждом изменении — если коллекция часто получает новые элементы вставкой в произвольную позицию (требующей либо повторной сортировки O(n log n), либо вставки в правильную позицию через lower_bound плюс insert, дающую O(n) для каждой вставки в vector), суммарная стоимость поддержания отсортированности может перевесить выгоду от быстрого O(log n) поиска, и для такого паттерна использования (частые вставки, частые поиски) может быть выгоднее использовать структуру, изначально поддерживающую и то, и другое эффективно (как std::set,).
• Путаница между lower_bound и upper_bound при поиске позиции для конкретной цели (вставка перед всеми равными элементами против вставки после всех равных элементов) — выбор неверного варианта даёт формально работающий, но не соответствующий реальному намерению код, особенно заметный при наличии дубликатов значения, для которого важен конкретный, определённый порядок относительно уже существующих равных элементов.
• Игнорирование того, что для очень небольших коллекций линейный поиск может быть практически быстрее бинарного из-за более низких констант и лучшей предсказуемости для процессора (простой последовательный перебор лучше предсказывается аппаратным предсказателем переходов процессора, чем «скачущий» по коллекции бинарный поиск) — для коллекций из нескольких элементов разница обычно непринципиальна, но это иллюстрирует общий урок о том, что асимптотическая сложность не учитывает константы, значимые именно для малых n.