26 Algorithms library [algorithms]

26.8 Sorting and related operations [alg.sorting]

26.8.4 Binary search [alg.binary.search]

26.8.4.5 binary_search [binary.search]

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
  constexpr bool
    binary_search(ForwardIterator first, ForwardIterator last,
                  const T& value);

template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
         class Compare>
  constexpr bool
    binary_search(ForwardIterator first, ForwardIterator last,
                  const T& value, Compare comp);

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
         class T = projected_value_t<I, Proj>,
         indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
                                       Proj proj = {});
template<forward_range R, class Proj = identity,
         class T = projected_value_t<iterator_t<R>, Proj>,
         indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
           ranges::less>
  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
                                       Proj proj = {});

Let comp be less{} and proj be identity{} for overloads with no parameters by those names.

Preconditions: The elements e of [first, last) are partitioned with respect to the expressions bool(invoke(comp, invoke(proj, e), value)) and !bool(invoke(comp, value, invoke(proj, e))).

Also, for all elements e of [first, last), bool(comp(e, value)) implies !bool(comp(value, e)) for the overloads in namespace std.

Returns: true if and only if for some iterator i in the range [first, last), !bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i))) is true.

Complexity: At most

log_{2} (last - first) + O (1)

comparisons and projections.