std::ranges::lower_bound

Объявлено в заголовочном файле `<algorithm>`
Сигнатура вызова
template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr I lower_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );	(1)	(начиная с C++20) (до C++26)
template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, class T = std::projected_value_t<I, Proj>, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr I lower_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );	(1)		(начиная с C++26)
template< ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t<R> lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );	(2)	(начиная с C++20) (до C++26)
template< ranges::forward_range R, class Proj = std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj> std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t<R> lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );	(2)		(начиная с C++26)

1) Возвращает итератор, указывающий на первый элемент диапазона [first, last), который не меньше (то есть больше или равен) value, либо last, если такой элемент не найден. Диапазон [first, last) должен быть разбит на разделы относительно выражения std::invoke(comp, std::invoke(proj, element), value), то есть все элементы, для которых выражение равно true, должны предшествовать всем элементам, для которых выражение равно false. Полностью отсортированный диапазон удовлетворяет этому условию.

2) То же, что и (1), но в качестве исходного диапазона используется r, как если бы ranges::begin(r) использовался как first, а ranges::end(r) — как last.

Описанные на этой странице функциональные объекты являются функциональными объектами алгоритмов (неофициально называемыми niebloids), то есть:

При вызове любого из них нельзя указывать явные списки аргументов шаблона.
Ни один из них не виден для поиска, зависящего от аргументов.
Если любой из них найден с помощью обычного неквалифицированного поиска в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

first, last	-	пара итератора и сентинела, задающая частично упорядоченный диапазон элементов для проверки
r	-	частично упорядоченный диапазон для проверки
value	-	значение, с которым сравниваются спроецированные элементы
comp	-	предикат сравнения, применяемый к спроецированным элементам
proj	-	проекция, применяемая к элементам

Возвращаемое значение

Итератор, указывающий на первый элемент, который не меньше value, либо last, если такой элемент не найден.

Сложность

Количество сравнений и применений проекции логарифмически зависит от расстояния между first и last (не более log₂(last - first) + O(1) сравнений и применений проекции). Однако для итератора, который не моделирует random_access_iterator, количество приращений итератора линейно.

Примечания

Для полностью отсортированного диапазона (или, в более общем случае, частично упорядоченного относительно value после проекции) std::ranges::lower_bound реализует алгоритм бинарного поиска. Поэтому std::ranges::binary_search можно реализовать на его основе.

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Инициализация списком для алгоритмов (1,2)

Возможная реализация

struct lower_bound_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<I, Proj>> Comp = ranges::less>
    constexpr I operator()(I first, S last, const T& value,
                           Comp comp = {}, Proj proj = {}) const
    {
        I it;
        std::iter_difference_t<I> count, step;
        count = std::ranges::distance(first, last);
        
        while (count > 0)
        {
            it = first;
            step = count / 2;
            ranges::advance(it, step, last);
            if (comp(std::invoke(proj, *it), value))
            {
                first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
    
    template<ranges::forward_range R, class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj>
          std::indirect_strict_weak_order
              <const T*, std::projected<ranges::iterator_t<R>,
                                        Proj>> Comp = ranges::less>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::ref(comp), std::ref(proj));
    }
};

inline constexpr lower_bound_fn lower_bound;

Пример

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>

namespace ranges = std::ranges;

template<std::forward_iterator I, std::sentinel_for<I> S, class T,
         class Proj = std::identity,
         std::indirect_strict_weak_order
             <const T*, std::projected<I, Proj>> Comp = ranges::less>
constexpr I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
{
    first = ranges::lower_bound(first, last, value, comp, proj);
    return first != last && !comp(value, proj(*first)) ? first : last;
}

int main()
{
    std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
    //                                 ^^^^^^^^^^
    auto lower = ranges::lower_bound(data, 4);
    auto upper = ranges::upper_bound(data, 4);

    std::cout << "found a range [" << ranges::distance(data.cbegin(), lower)
              << ", " << ranges::distance(data.cbegin(), upper) << ") = { ";
    ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "}\n";

    // classic binary search, returning a value only if it is present

    data = {1, 2, 4, 8, 16};
    //               ^
    auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end()

    if (it != data.cend())
        std::cout << *it << " found at index " << ranges::distance(data.cbegin(), it);

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it2 = ranges::lower_bound(nums, {2, 0}, cmpz);
    #else
        auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it2 == CD{2, 2}));
}

Вывод:

found a range [6, 10) = { 4 4 4 4 }
8 found at index 3

См. также

ranges::equal_range (C++20)	находит диапазон элементов, равных заданному значению, с помощью бинарного поиска (функциональный объект алгоритма)
ranges::partition (C++20)	разделяет диапазон элементов на две группы (функциональный объект алгоритма)
ranges::partition_point (C++20)	находит точку разделения в разделённом диапазоне (функциональный объект алгоритма)
ranges::upper_bound (C++20)	находит первый элемент, больший заданного значения, с помощью бинарного поиска (функциональный объект алгоритма)
lower_bound	находит первый элемент, не меньший заданного значения, с помощью бинарного поиска (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/lower_bound