From cppreference.com
Defined in header
Call signature
template<std::forward_iteratorI,std::sentinel_for<I>S,classT,classProj=std::identity,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprboolbinary_search(Ifirst,Slast,constT&value,Compcomp={},Projproj={}); (1)(since C++20)
(until C++26)template<std::forward_iteratorI,std::sentinel_for<I>S,classProj=std::identity,classT=std::projected_value_t<I,Proj>,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprboolbinary_search(Ifirst,Slast,constT&value,Compcomp={},Projproj={});(since C++26)template<ranges::forward_rangeR,classT,classProj=std::identity,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprboolbinary_search(R&&r,constT&value,Compcomp={},Projproj={}); (2)(since C++20)
(until C++26)template<ranges::forward_rangeR,classProj=std::identity,classT=std::projected_value_t<ranges::iterator_t<R>,Proj>,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprboolbinary_search(R&&r,constT&value,Compcomp={},Projproj={});(since C++26)Checks if an element equivalent to value exists in the partitioned source range [first, last) or r. An element is considered equivalent to value if its projected value neither orders before nor orders after value with the comparator comp.
If the elements e of the source range are not partitioned with respect the following expressions at the same time, the behavior is undefined:
bool(std::invoke(comp,std::invoke(proj,e),value))
!bool(std::invoke(comp,value,std::invoke(proj,e)))
The function-like entities described on this page are
(informally known as niebloids), that is:
Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to
.
When any of them are found by
as the name to the left of the function-call operator,
is inhibited.
Parameters
first, last - the iterator-sentinel pair defining the source
r - the source range value - the value to be compared with the (projected) elements comp - the comparator to be applied to the (projected) elements proj - the projection to be applied to the elements Return value
true if an element equivalent to value exists, false otherwise.
Complexity
Given N as ranges::distance(first,last) or ranges::distance(r):
1,2) At most log2(N)+𝓞(1) applications of comp and proj.
Notes
ranges::binary_search doesn't return an iterator to the found element when an element whose projection equals value is found. To obtain an iterator to that element (if exists),
should be used instead.
macroValueStdFeature
__cpp_lib_algorithm_default_value_type
(C++26)
for algorithms (
)Possible implementation
structbinary_search_fn{template<std::forward_iteratorI,std::sentinel_for<I>S,classProj=std::identity,classT=std::projected_value_t<I,Proj>,std::indirect_strict_weak_order<constT*,std::projected<I,Proj>>Comp=ranges::less>constexprbooloperator()(Ifirst,Slast,constT&value,Compcomp={},Projproj={})const{autox=ranges::lower_bound(first,last,value,comp,proj);return(!(x==last)&&!(std::invoke(comp,value,std::invoke(proj,*x))));}template<ranges::forward_rangeR,classProj=std::identity,classT=std::projected_value_t<ranges::iterator_t<R>,Proj>,std::indirect_strict_weak_order<constT*,std::projected<ranges::iterator_t<R>,Proj>>Comp=ranges::less>constexprbooloperator()(R&&r,constT&value,Compcomp={},Projproj={})const{return(*this)(ranges::begin(r),ranges::next(ranges::begin(r),ranges::end(r)),value,std::move(comp),std::move(proj));}};inlineconstexprbinary_search_fnbinary_search;Example
Run this code
#include<algorithm>#include<cassert>#include<complex>#include<iostream>#include<ranges>#include<vector>intmain(){constexprstaticautohaystack={1,3,4,5,9};static_assert(std::ranges::is_sorted(haystack));for(constintneedle: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";}usingCD=std::complex<double>;std::vector<CD>nums{{1,1},{2,3},{4,2},{4,3}};autocmpz=[](CDx,CDy){returnabs(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}Output:
Searching for 1: found 1 Searching for 2: no dice! Searching for 3: found 3 See also