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

• partitioned with respect tostd::invoke(comp,std::invoke(proj, element), value) (that is, all projected elements for which the expression istrue precedes all elements for which the expression isfalse).
• partitioned with respect to!std::invoke(comp, value,std::invoke(proj, element)).
• for all elements, ifstd::invoke(comp,std::invoke(proj, element), value) istrue then!std::invoke(comp, value,std::invoke(proj, element)) is alsotrue.

A fully-sorted range meets these criteria.

The function-like entities described on this page arealgorithm function objects (informally known asniebloids), that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible toargument-dependent lookup.
• When any of them are found bynormal 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 tovalue is found,false otherwise.

[edit]Complexity

The number of comparisons and projections performed is logarithmic in the distance betweenfirst andlast (at mostlog2(last - first) + O(1) comparisons and projections). However, for iterator-sentinel pair that does not modelstd::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 equalsvalue 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>constexprbool 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>constexprbool 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));}}; inlineconstexpr binary_search_fn binary_search;

[edit]Example

#include <algorithm>#include <cassert>#include <complex>#include <iostream>#include <ranges>#include <vector> int main(){constexprstaticauto haystack={1,3,4,5,9};    static_assert(std::ranges::is_sorted(haystack)); for(constint 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_typeassert(std::ranges::binary_search(nums,{4,2}, cmpz));#elseassert(std::ranges::binary_search(nums, CD{4,2}, cmpz));#endif}

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

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文