std::ranges::binary_search

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 bool binary_search( I first, S last, const T& value,
                              Comp comp = {}, Proj proj = {} );

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 bool binary_search( I first, S last, const T& value,
                              Comp comp = {}, Proj proj = {} );

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 bool binary_search( R&& r, const T& value,
                              Comp comp = {}, Proj proj = {} );

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 bool binary_search( R&& r, const T& value,
                              Comp comp = {}, Proj proj = {} );

Для успешного выполнения ranges::binary_search диапазон [first, last) должен быть по крайней мере частично упорядочен относительно value, т.е. он должен удовлетворять всем следующим требованиям:

• разбит относительно std::invoke(comp, std::invoke(proj, element), value) (то есть все спроецированные элементы, для которых выражение true, предшествуют всем элементам, для которых выражение false).
• разбит относительно !std::invoke(comp, value, std::invoke(proj, element)).
• для всех элементов, если std::invoke(comp, std::invoke(proj, element), value) равно true, то !std::invoke(comp, value, std::invoke(proj, element)) также равно true.

Полностью отсортированный диапазон удовлетворяет этим критериям.

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

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

Параметры

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

true true, если найден элемент, равный value, иначе false.

Сложность

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

Примечания

std::ranges::binary_search не возвращает итератор на найденный элемент, когда найден элемент, проекция которого равна value. Если требуется итератор, следует использовать std::ranges::lower_bound.

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

struct binary_search_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 bool operator()(I first, S last, const T& value,
                              Comp comp = {}, Proj proj = {}) const
    {
        auto x = ranges::lower_bound(first, last, value, comp, proj);
        return (!(x == last) && !(std::invoke(comp, value, std::invoke(proj, *x))));
    }
    
    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 bool operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::move(comp), std::move(proj));
    }
};

inline constexpr binary_search_fn binary_search;

Пример

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

int main()
{
    constexpr static auto haystack = {1, 3, 4, 5, 9};
    static_assert(std::ranges::is_sorted(haystack));
    
    for (const int needle : std::views::iota(1)
                          | std::views::take(3))
    {
        std::cout << "Searching for " << needle << ": ";
        std::ranges::binary_search(haystack, needle)
            ? std::cout << "found " << needle << '\n'
            : std::cout << "no dice!\n";
    }

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::ranges::binary_search(nums, {4, 2}, cmpz));
    #else
        assert(std::ranges::binary_search(nums, CD{4, 2}, cmpz));
    #endif
}

Searching for 1: found 1
Searching for 2: no dice!
Searching for 3: found 3

Смотрите также