std::ranges::binary_search
Defined in header <algorithm>
|
||
Call signature |
||
template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, |
(1) | (since C++20) |
template< ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order< |
(2) | (since C++20) |
value
appears within the range [first, last)
.r
as the source range, as if using ranges::begin(r) as first
and ranges::end(r) as last
.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 niebloids, that is:
- Explicit template argument lists may not be specified when calling any of them.
- None of them is visible to argument-dependent lookup.
- When one of them is found by normal unqualified lookup for the name to the left of the function-call operator, it inhibits argument-dependent lookup.
In practice, they may be implemented as function objects, or with special compiler extensions.
Parameters
first, last | - | the range of elements to examine |
r | - | the range of elements to examine |
value | - | value to compare the elements to |
comp | - | comparison function to apply to the projected elements |
proj | - | projection to apply to the elements |
Return value
true if an element equal to value
is found, false otherwise.
Complexity
The number of comparisons and projections performed is logarithmic in the distance between first
and last
(At most log
2(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.
Possible implementation
struct binary_search_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, 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 { first = std::lower_bound(first, last, value, comp); return (!(first == last) && !(comp(value, *first))); } template<ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order< const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less> constexpr bool operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), value, std::ref(comp), std::ref(proj)); } }; inline constexpr binary_search_fn binary_search; |
Example
#include <algorithm> #include <iostream> int main() { constexpr static auto haystack = {1, 3, 4, 5, 9}; constexpr static auto needles = {1, 2, 3}; for (const int needle : needles) { std::cout << "Searching for " << needle << ": "; std::ranges::binary_search(haystack, needle) ? std::cout << "found " << needle << '\n' : std::cout << "no dice!\n"; } }
Output:
Searching for 1: found 1 Searching for 2: no dice! Searching for 3: found 3
See also
(C++20) |
returns range of elements matching a specific key (niebloid) |
(C++20) |
returns an iterator to the first element not less than the given value (niebloid) |
(C++20) |
returns an iterator to the first element greater than a certain value (niebloid) |
determines if an element exists in a certain range (function template) |