std::binary_search, std::lower_bound, std::upper_bound

1. Зачем нужен бинарный поиск

Когда вы только начинаете программировать, кажется, что поиск — это всегда «пробегись циклом и сравни». И это правда… ровно до того момента, пока данных мало, а время не жалко. Но как только у вас появляется хотя бы несколько тысяч элементов, а поиск делается много раз (например, по каждому действию пользователя), линейный поиск начинает раздражать — примерно как компиляция проекта на ноутбуке в режиме “Release + LTO”, когда вы просто хотели проверить одну строчку.

Бинарный поиск — это способ искать в отсортированных данных за логарифмическое время. Интуитивно это означает: вместо того чтобы проверять элементы по одному, мы каждый раз «выкидываем» половину диапазона. В отсортированном массиве это работает идеально: посмотрели на середину — поняли, где искать дальше.

Важно: в STL бинарный поиск — это не одна функция, а семейство алгоритмов. У них разные цели:

• std::binary_search отвечает «есть ли такой элемент вообще?»
• std::lower_bound отвечает «где должен стоять элемент (первая позиция, где он мог бы появиться)?»
• std::upper_bound отвечает «где заканчиваются все элементы, эквивалентные этому ключу?»

И сегодня мы научимся читать их результаты правильно — без гаданий и без шаманства.

2. Предусловие: сортировка тем же порядком

Бинарный поиск — алгоритм очень честный: он не делает вид, что понимает ваш мир. Он верит в одну вещь — что диапазон уже отсортирован. Причём не «примерно», не «как-то», а строго тем же правилом, которое используется в поиске. Если отсортировали по возрасту, а ищете по имени — это уже другой порядок, и бинарный поиск превращается в генератор случайных ответов (почти как студент, который отвечает на экзамене по билетам, которые он не учил).

Давайте зафиксируем это как мантру дня:

Сортировка и бинарный поиск должны использовать один и тот же порядок (тот же operator< или тот же компаратор).

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

flowchart TD
    A[Есть диапазон элементов] --> B{Он отсортирован?}
    B -- нет --> C[Бинарный поиск не имеет смысла: ответ может быть неверным]
    B -- да --> D{Правило сортировки = правило поиска?}
    D -- нет --> C
    D -- да --> E[Можно применять binary_search / lower_bound / upper_bound]

На практике это означает простую дисциплину: если у вас есть компаратор comp, используйте его же и в std::sort, и в std::lower_bound, и в std::upper_bound. Не «похожий», не «почти такой же», а буквально тот же.

3. Алгоритмы поиска в STL

std::binary_search: ответ «есть/нет»

std::binary_search(first, last, value) возвращает bool. Он не говорит, где элемент лежит, сколько таких элементов, и почему жизнь вообще устроена так несправедливо. Он говорит только: «по этому порядку в этом отсортированном диапазоне есть элемент, эквивалентный value».

Начнём с простого примера на числах — так проще увидеть механику.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 4, 4, 7};

    std::cout << std::binary_search(v.begin(), v.end(), 4) << "\n"; // 1
    std::cout << std::binary_search(v.begin(), v.end(), 5) << "\n"; // 0
}

Здесь важно, что v уже отсортирован. Если вы сделаете std::vector<int> v{4, 1, 7, 2, 4};, то binary_search не обязан работать правильно: он будет «делить пополам» мусорный порядок и делать неправильные выводы.

Когда binary_search удобен? Когда вам нужно быстро ответить «есть ли такой ключ» и больше ничего. Например, «есть ли задача с id=42» — да/нет. Если вам нужна позиция, вы почти всегда переходите к lower_bound.

std::lower_bound: позиция вставки и кандидат на совпадение

std::lower_bound(first, last, value) возвращает итератор на первый элемент, который не меньше value (в терминах operator<). В более человеческом виде это звучит так: «покажи место, куда можно вставить value, чтобы порядок не сломался».

И вот тут у новичков часто ломается мозг: lower_bound — это не «поиск элемента», это «поиск границы». Он может вернуть итератор на существующий элемент, а может вернуть позицию вставки. Поэтому после lower_bound часто нужна проверка: «а это точно он?».

Покажем на примере:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 4, 4, 7};

    auto it = std::lower_bound(v.begin(), v.end(), 3);
    std::cout << (it - v.begin()) << "\n"; // 2 (между 2 и 4)
}

Значение 3 вектора не содержит, но lower_bound нашёл позицию, где оно должно стоять: индекс 2.

А вот если ищем 4:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 4, 4, 7};

    auto it = std::lower_bound(v.begin(), v.end(), 4);
    std::cout << (it - v.begin()) << "\n"; // 2
}

Почему индекс 2? Потому что это первая 4. И это уже намекает, что lower_bound удобно использовать для работы с дубликатами: он всегда указывает на левую границу группы «одинаковых по ключу» элементов.

std::upper_bound: правая граница для дубликатов

std::upper_bound(first, last, value) возвращает итератор на первый элемент, который больше value. Если lower_bound — левая граница группы, то upper_bound — правая граница (точнее, позиция после группы).

Снова на примере с несколькими 4:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 4, 4, 4, 7};

    auto lo = std::lower_bound(v.begin(), v.end(), 4);
    auto hi = std::upper_bound(v.begin(), v.end(), 4);

    std::cout << (hi - lo) << "\n"; // 3
}

Здесь (hi - lo) — количество элементов, эквивалентных 4. Это очень практичный трюк: не надо руками считать, не надо бегать циклом, и вы не перепутаете «включительно/исключительно», потому что диапазон в STL почти всегда полуинтервальный: [lo, hi).

4. Диапазон [lo, hi) для дубликатов

Когда вы начинаете работать с контейнерами, вы привыкаете к вопросу «где элемент». Но в реальных данных часто встречается вопрос «где все элементы с таким ключом». Например: «все задачи со статусом Done», «все товары с ценой 100», «все люди с возрастом 30». И вот тут пара lower_bound/upper_bound становится очень мощной.

Давайте закрепим идею рисунком. Пусть v отсортирован, а x = 4:

индексы: 0 1 2 3 4 5
v:      1 2 4 4 4 7
           ^     ^
          lo     hi
Диапазон "всех 4": [lo, hi) = индексы 2..4

Практическая польза: у нас появляется стандартизированная «зона интереса». Мы можем делать по ней что угодно: вывести, посчитать, обработать. Важно лишь помнить: чтобы разыменовать итератор, нужно проверять, что он не равен end().

5. Поиск по struct и пример TaskBox

Теперь перейдём к более реалистичному коду. Представим, что мы продолжаем наше учебное консольное приложение TaskBox — мини-менеджер задач. Раньше мы хранили задачи в std::vector<Task>, сортировали их и печатали. Теперь мы хотим быстро находить задачу по id.

Модель:

#include <string>

struct Task {
    int id{};
    std::string title;
};

Сортируем по id — значит и искать будем по id.

#include <algorithm>
#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
};

int main() {
    std::vector<Task> tasks{{2, "Read"}, {5, "Sleep"}, {3, "Code"}};

    auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
    std::sort(tasks.begin(), tasks.end(), comp);
}

Поиск по Task через lower_bound

Окей. Теперь поиск. Ловушка: lower_bound требует value того же типа, что и элементы (в классической перегрузке). Проще всего сделать «ключевой объект» Task{wantedId, ""}. Строка нам не важна, потому что компаратор сравнивает только id.

#include <algorithm>
#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
};

int main() {
    std::vector<Task> tasks{{2, "Read"}, {3, "Code"}, {5, "Sleep"}};
    auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };

    Task key{3, ""};
    auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);
}

Но даже если it != tasks.end(), это ещё не означает «нашли задачу». lower_bound мог вернуть позицию вставки. Поэтому мы проверяем совпадение по id:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
};

int main() {
    std::vector<Task> tasks{{2, "Read"}, {3, "Code"}, {5, "Sleep"}};
    auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };

    Task key{4, ""};
    auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);

    bool found = (it != tasks.end() && it->id == 4);
    std::cout << found << "\n"; // 0
}

Эта проверка — обязательная часть «ритуала», и это нормальный ритуал. В C++ много ритуалов, но этот хотя бы полезный.

Поддерживаем отсортированность: find и upsert

Теперь сделаем шаг к коду, который действительно похож на «кусок приложения», а не на отдельный пример. Мы хотим две операции:

• Найти задачу по id (быстро).
• Добавить задачу так, чтобы tasks оставался отсортированным по id.

Почему второе важно? Потому что если вы один раз отсортировали, а потом делаете push_back, порядок ломается, и бинарный поиск уже нельзя применять честно.

Сделаем функцию поиска. Для простоты вернём указатель Task* (или nullptr, если не нашли). Мы уже обсуждали указатели как nullable-контракт ранее в курсе.

#include <algorithm>
#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
};

Task* find_task_by_id(std::vector<Task>& tasks, int id) {
    auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };
    Task key{id, ""};

    auto it = std::lower_bound(tasks.begin(), tasks.end(), key, comp);
    if (it == tasks.end() || it->id != id) return nullptr;
    return &(*it);
}

Обратите внимание: мы не возвращаем итератор наружу (чтобы не усложнять жизнь), а возвращаем понятный «либо есть, либо нет» указатель.

Теперь добавление. Мы находим позицию вставки через lower_bound. Если id уже существует — обновим задачу (например, поменяем title). Если нет — вставим в найденную позицию, чтобы порядок сохранился.

#include <algorithm>
#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
};

void upsert_task(std::vector<Task>& tasks, Task t) {
    auto comp = [](const Task& a, const Task& b) { return a.id < b.id; };

    auto it = std::lower_bound(tasks.begin(), tasks.end(), t, comp);
    if (it != tasks.end() && it->id == t.id) {
        it->title = t.title;           // обновили существующую
    } else {
        tasks.insert(it, std::move(t)); // вставили на правильное место
    }
}

Да, insert у vector может быть не самым быстрым (элементы сдвигаются), но сегодня наша цель — корректность модели и правильное применение бинарного поиска. Оптимизация — это следующая ступень, а не первая (иначе вы оптимизируете то, что и так неверно, и получаете «быстро неверно»).

Проверим, что всё работает, маленьким main:

#include <iostream>
#include <vector>
#include <string>

struct Task {
    int id{};
    std::string title;
};

Task* find_task_by_id(std::vector<Task>& tasks, int id);
void upsert_task(std::vector<Task>& tasks, Task t);

int main() {
    std::vector<Task> tasks{{2, "Read"}, {5, "Sleep"}};

    upsert_task(tasks, Task{3, "Code"});
    upsert_task(tasks, Task{5, "Sleep more"});

    Task* t = find_task_by_id(tasks, 5);
    std::cout << (t ? t->title : "not found") << "\n"; // Sleep more
}

Заметьте важный момент: мы ни разу не вызывали sort после вставок. Мы поддерживаем отсортированность «в процессе жизни контейнера». Это делает бинарный поиск честным, а код — предсказуемым.

6. Типичные ошибки при работе с binary_search, lower_bound, upper_bound

Ошибка №1: применять бинарный поиск к неотсортированным данным.
Это самая частая ошибка, потому что внешне всё выглядит правдоподобно: код компилируется, программа иногда «находит», иногда «не находит», и вы начинаете подозревать заговор компьютера. На самом деле компьютер не виноват: бинарный поиск требует сортировку как предусловие. Если порядок сломан — результат не обязан быть корректным.

Ошибка №2: сортировать одним правилом, а искать другим.
Это тонкая версия первой ошибки. Например, вы отсортировали Task по id, а потом решили искать по title через lower_bound (или наоборот). Вы можете даже «примерно угадать» — и всё равно получить неверные позиции. Лечится дисциплиной: один и тот же компаратор (или один и тот же порядок) должен жить и в sort, и в lower_bound/upper_bound.

Ошибка №3: считать, что it != end() после lower_bound означает «элемент найден».
lower_bound возвращает позицию вставки. Если вы ищете 4, а вектор содержит 1 2 7, то позиция вставки будет где-то внутри диапазона, и it != end() будет истинным. Но элемента 4 всё равно нет. Поэтому нужна дополнительная проверка «точного совпадения» (например, it->id == wantedId).

Ошибка №4: разыменовывать итератор без проверки на end().
Эта ошибка особенно коварна, потому что на тестовых данных часто «везёт». Но если элемент должен вставляться в конец, lower_bound вернёт end(), и попытка сделать it->id закончится плохо. Правило простое: итератор можно разыменовывать только если он не равен end().

Ошибка №5: забыть про дубликаты и пытаться получить «любой» элемент, когда нужны «все».
Если данные могут содержать повторяющиеся ключи, то binary_search даст только «да/нет», а lower_bound даст левую границу. Если по смыслу вам нужно обработать все элементы с данным ключом, правильная модель — диапазон [lower_bound, upper_bound). Если вы делаете только lower_bound и берёте один элемент, вы иногда будете «терять» остальные и долго не понимать, почему отчёты не сходятся.