Daily bit(e) C++. std::lower_bound, std::upper_bound
Daily bit(e) C++ 123, два алгоритма бинарного поиска – std::lower_bound и std::upper_bound.
std::lower_bound и std::upper_bound – пожалуй, два самых практически полезных алгоритма стандартной библиотеки.
Оба алгоритма реализуют бинарный поиск и работают за время O(log n) на отсортированных диапазонах.
std::lower_bound возвращает итератор на первый элемент, который не предшествует заданному значению (то есть первый элемент, который не меньше заданного), а std::upper_bound – на первый элемент, следующий после заданного значения (первый элемент, который строго больше заданного).
Обратите внимание: количество сравнений остается равным O(log n) даже для диапазонов, не поддерживающих произвольный доступ. Однако количество операций инкремента итератора составляет O(n).
#include <algorithm>
#include <vector>
std::vector<int> data{1,2,3,4,5,5,5,6,7,8,9};
// Первый элемент, для которого элемент < значение == false
auto lb = std::lower_bound(data.begin(), data.end(), 5);
// *lb == 5
// то же самое:
lb = std::partition_point(data.begin(), data.end(), [](int el) {
return el < 5;
});
// *lb == 5
// Первый элемент, для которого значение < элемент == true
auto ub = std::ranges::upper_bound(data, 5); // версия для диапазонов
// *ub == 6
// то же самое:
ub = std::ranges::partition_point(data, [](int el) {
return not (5 < el);
});
// *ub == 6
// [begin, lb) формирует поддиапазон из элементов меньше
// заданного значения
auto lower = std::ranges::subrange(data.begin(), lb);
// lower == {1, 2, 3, 4}
// [lb, ub) формирует поддиапазон из элементов, равных
// заданному значению
auto equal = std::ranges::subrange(lb, ub);
// equal == {5, 5, 5}
// [ub, end) формирует поддиапазон из элементов больше
// заданного значения
auto high = std::ranges::subrange(ub, data.end());
// high == {6, 7, 8, 9}
std::vector<std::string> strs{"a","ab","fge","cdefgh"};
// Найти первую строку длиной не менее 2 символов
auto el = std::ranges::lower_bound(strs, 2,
std::less<>{}, // пользовательский компаратор
[](const std::string& el) { // проекция
return el.length();
});
// *el == "ab"