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< 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 = {} );

For ranges::binary_search to succeed, the range [first, last) must be at least partially ordered with respect to value, i.e. it must satisfy all of the following requirements:

• partitioned with respect to std::invoke(comp, std::invoke(proj, element), value) (that is, all projected elements for which the expression is true precedes all elements for which the expression is false).
• partitioned with respect to !std::invoke(comp, value, std::invoke(proj, element)).
• for all elements, if std::invoke(comp, std::invoke(proj, element), value) is true then !std::invoke(comp, value, std::invoke(proj, element)) is also true.

A fully-sorted range meets these criteria.

The function-like entities described on this page are niebloids, that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible to argument-dependent lookup.
• When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions.

Parameters

Return value

true if an element equal to value is found, false otherwise.

Complexity

The number of comparisons and projections performed is logarithmic in the distance between first and last (at most log₂(last - first) + O(1) comparisons and projections). However, for iterator-sentinel pair that does not model std::random_access_iterator, number of iterator increments is linear.

Possible implementation

struct binary_search_fn
{
    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
        operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        first = std::lower_bound(first, last, value, comp);
        return (!(first == last) && !(comp(value, *first)));
    }
 
    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 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 binary_search_fn binary_search;

Example

#include <algorithm>
#include <iostream>
#include <ranges>
 
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";
    }
}

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

See also