Przejdź do głównej zawartości

std::ranges::binary_search() algorithm

// (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)

  • T - (none)

  • Proj - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

  • (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, or last if no such element is found.

    The range [first; last) must be partitioned with respect to the expression comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false.

    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 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.

  • (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.

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

Main.cpp
#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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::binary_search() algorithm

// (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)

  • T - (none)

  • Proj - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

  • (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, or last if no such element is found.

    The range [first; last) must be partitioned with respect to the expression comp(element, value), i.e., all elements for which the expression is true must precede all elements for which the expression is false.

    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 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.

  • (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.

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

Main.cpp
#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
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.