std::ranges::binary_search

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 algorithm function objects (informally known as 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.

[edit] Parameters

[edit] Return value

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

[edit] Complexity

The number of comparisons and projections performed is logarithmic in the distance between first and last (at most log2(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.

[edit] Notes

std::ranges::binary_search doesn't return an iterator to the found element when an element whose projection equals value is found. If an iterator is desired, std::ranges::lower_bound should be used instead.

[edit] Possible implementation

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::