Mediumалгоритмы
Чем std::lower_bound и std::upper_bound полезны?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Работают на отсортированном диапазоне, O(log n). std::lower_bound — первый элемент >= x. std::upper_bound — первый элемент > x.
std::vector<int> v{1, 2, 2, 2, 3, 4};
auto lb = std::lower_bound(v.begin(), v.end(), 2); // первый >= 2
auto ub = std::upper_bound(v.begin(), v.end(), 2); // первый > 2
// [lb, ub) — все элементы, равные 2
// Вставка с сохранением порядка
v.insert(std::lower_bound(v.begin(), v.end(), 2), 2);
// equal_range — сразу пара (lower, upper)
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 2);- В отличие от
std::find(O(n)), binary search — O(log n); - Для unordered контейнеров не работают (нет порядка) — там метод
find().
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.