std::ranges::binary_search() algorithm
- since C++20
- Simplified
- Detailed
// (1)
constexpr bool
binary_search( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );
// (2)
constexpr bool
binary_search( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
The type of arguments are generic and have the following constraints:
-
I
-std::forward_iterator
-
S
-std::sentinel_for<I>
-
R
-std::ranges::forward_range
-
Comp
:- (1) -
indirect_strict_weak_order< const T*, projected<I, Proj>>
- (2) -
indirect_strict_weak_order< const T*, projected<ranges::iterator_t<R>, Proj>>
(The
std::
namespace was ommitted here for readability) - (1) -
-
T
- (none) -
Proj
- (none)
The Proj
and Comp
template arguments have the following default types: std::identity
, ranges::less
for all overloads.
// (1)
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
binary_search( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );
// (2)
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
binary_search( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
-
(1) Returns an iterator pointing to the first element in the range [
first
;last
) that is not less than (i.e. greater or equal to)value
, orlast
if no such element is found.The range [
first
;last
) must be partitioned with respect to the expressioncomp(element, value)
, i.e., all elements for which the expression istrue
must precede all elements for which the expression isfalse
.A fully-sorted range meets this criterion.
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 istrue
precedes all elements for which the expression isfalse
). - Partitioned with respect to
!std::invoke(comp, value, std::invoke(proj, element))
. - For all elements, if
std::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.
-
(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 usingranges::begin(r)
asfirst
andranges::end(r)
aslast
.
The function-like entities described on this page are niebloids.
Parameters
first last | The partially-ordered range of elements to examine. |
r | The partially-ordered range of elements to examine. |
value | The value to compare the elements to. |
comp | Comparison function to apply to the projected elements. |
proj | Projection to apply to the elements. |
Return value
If an element equal to value
is found, true
.
Otherwise, false
.
Complexity
At most log2(last - first) + O(1) comparisons and applications of the projection.
However, for an iterator that does not model random_access_iterator
, the number of iterator increments is linear.
Exceptions
(none)
Possible implementation
ranges::binary_search
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;
Examples
#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";
}
}
Searching for 1: found 1
Searching for 2: no dice!
Searching for 3: found 3
Hover to see the original license.