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>constexprIlower_bound(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>constexprIlower_bound(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>constexprranges::borrowed_iterator_t<R>lower_bound(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>constexprranges::borrowed_iterator_t<R>lower_bound(R&&r,constT&value,Compcomp={},Projproj={});(since C++26)Searches for the first element (projected by proj) in the partitioned source range [first, last) or r which is not ordered before value with the comparator comp.
If the elements e of the source range are not partitioned with respect to the expression bool(std::invoke(comp,std::invoke(proj,e),value)), the behavior is undefined.
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
Iterator to the first element which is not ordered before value, or the past-the-end iterator of the source range if no such element is found.
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
macroValueStdFeature
__cpp_lib_algorithm_default_value_type
(C++26)
for algorithms (
)Possible implementation
structlower_bound_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>constexprIoperator()(Ifirst,Slast,constT&value,Compcomp={},Projproj={})const{Iit;std::iter_difference_t<I>count,step;count=std::ranges::distance(first,last);while(count>0){it=first;step=count/2;ranges::advance(it,step,last);if(comp(std::invoke(proj,*it),value)){first=++it;count-=step+1;}elsecount=step;}returnfirst;}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>constexprranges::borrowed_iterator_t<R>operator()(R&&r,constT&value,Compcomp={},Projproj={})const{return(*this)(ranges::begin(r),ranges::next(ranges::begin(r),ranges::end(r)),value,std::ref(comp),std::ref(proj));}};inlineconstexprlower_bound_fnlower_bound;Example
Run this code
#include<algorithm>#include<cassert>#include<complex>#include<iostream>#include<iterator>#include<vector>namespaceranges=std::ranges;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>constexprIbinary_find(Ifirst,Slast,constT&value,Compcomp={},Projproj={}){first=ranges::lower_bound(first,last,value,comp,proj);returnfirst!=last&&!comp(value,proj(*first))?first:last;}intmain(){std::vectordata{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5};// ^^^^^^^^^^autolower=ranges::lower_bound(data,4);autoupper=ranges::upper_bound(data,4);std::cout<<"found a range ["<<ranges::distance(data.cbegin(),lower)<<", "<<ranges::distance(data.cbegin(),upper)<<") = { ";ranges::copy(lower,upper,std::ostream_iterator<int>(std::cout," "));std::cout<<"}\n";// classic binary search, returning a value only if it is presentdata={1,2,4,8,16};// ^autoit=binary_find(data.cbegin(),data.cend(),8);// “5” would return end()if(it!=data.cend())std::cout<<*it<<" found at index "<<ranges::distance(data.cbegin(),it);usingCD=std::complex<double>;std::vector<CD>nums{{1,0},{2,2},{2,1},{3,0}};autocmpz=[](CDx,CDy){returnx.real()<y.real();};#ifdef __cpp_lib_algorithm_default_value_typeautoit2=ranges::lower_bound(nums,{2,0},cmpz);#elseautoit2=ranges::lower_bound(nums,CD{2,0},cmpz);#endifassert((*it2==CD{2,2}));}Output:
found a range [6, 10) = { 4 4 4 4 } 8 found at index 3 See also
finds the first element not less than the given value using binary search
(function template)
(C++20)
finds the range of elements matching the given value using binary search
(algorithm function object)
(C++20)
divides a range of elements into two groups
(algorithm function object)
(C++20)
locates the partition point of a partitioned range
(algorithm function object)
(C++20)
finds the first element greater than the given value using binary search
(algorithm function object)