C++ алгоритм std::lower_bound. Ищет первый элемент в последовательности который равный или больше заданного. Описание, пример использования.

std::lower_bound

Актуально для C++23.

#include <algorithm>

Актуально на 2024-03-05.

Define overload #1

template<class ForwardIterator, class Tp>
constexpr inline ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const Tp& value);

Ищет первый элемент в последовательности [first, last], который >= "value".
Последовательность [first, last] должна быть отсортированна в порядке возрастания.
Вернёт итератор на этот элемент или last, если подходящего значения не нашлось.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation

Define overload #2

template<class ForwardIterator, class Tp, class Compare>
constexpr ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last,
            const Tp& value, Compare comp);

Ищет первый элемент в последовательности [first, last], для которого бинарный предикат comp(elem < value) возвратит false.
Последовательность [first, last] должна быть отсортированна в порядке возрастания.
Вернёт итератор на этот элемент или last, если подходящего значения не нашлось.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation

Examples

Example 1:

#include <iostream>
#include <algorithm>

int main()
{
    auto data = {0, 1, 3, 5, 7, 9};
    auto it = std::lower_bound(std::begin(data), std::end(data), 2);
    if (it != std::end(data))
    {
        std::cout << *it << std::endl;
    }
    return 0;
}

Changelog

C++26
TODO

C++23
TODO

C++20
TODO

C++17
TODO

C++14
TODO

C++11
TODO

See also

TODO

This page was last modified on 2024-03-05