table of contents
std::ranges::binary_search(3) | C++ Standard Libary | std::ranges::binary_search(3) |
NAME¶
std::ranges::binary_search - std::ranges::binary_search
Synopsis¶
Defined in header <algorithm>
Call signature
template< std::forward_iterator I, std::sentinel_for<I> S, class
T,
class Proj = std::identity,
std::indirect_strict_weak_order<
const T*, (1) (since C++20)
std::projected<I, Proj>> Comp = ranges::less >
constexpr bool
binary_search( I first, S last, const T& value, Comp comp = {},
Proj proj = {} );
template< ranges::forward_range R, class T, class Proj =
std::identity,
std::indirect_strict_weak_order<
const T*, (2) (since C++20)
std::projected<ranges::iterator_t<R>, Proj>> Comp =
ranges::less >
constexpr bool
binary_search( R&& r, const T& value, Comp comp = {}, Proj proj =
{} );
1) Checks if a projected element equivalent to value appears within the range
[first, last).
2) Same as (1), but uses 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¶
// Run this code
#include <algorithm>
#include <iostream>
#include <ranges>
int main()
{
constexpr static auto haystack = {1, 3, 4, 5, 9};
static_assert(std::ranges::is_sorted(haystack));
for (const int 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";
}
}
Output:¶
Searching for 1: found 1
Searching for 2: no dice!
Searching for 3: found 3
See also¶
ranges::equal_range returns range of elements matching a specific
key
(C++20) (niebloid)
ranges::lower_bound returns an iterator to the first element not less than
the
(C++20) given value
(niebloid)
ranges::upper_bound returns an iterator to the first element greater than a
(C++20) certain value
(niebloid)
ranges::contains
ranges::contains_subrange checks if the range contains the given element or
subrange
(C++23) (niebloid)
(C++23)
determines if an element exists in a partially-ordered
binary_search range
(function template)
2022.07.31 | http://cppreference.com |