Binary Search

Groups

template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE ForwardIterator lower_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <class ForwardIterator,   class LessThanComparable> ForwardIterator lower_bound(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE ForwardIterator lower_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <class ForwardIterator,   class T,   class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE ForwardIterator upper_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <class ForwardIterator,   class LessThanComparable> ForwardIterator upper_bound(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE ForwardIterator upper_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <class ForwardIterator,   class T,   class StrictWeakOrdering> ForwardIterator upper_bound(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE bool binary_search(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <class ForwardIterator,   class LessThanComparable> bool binary_search(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE bool binary_search(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <class ForwardIterator,   class T,   class StrictWeakOrdering> bool binary_search(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE thrust::pair< ForwardIterator, ForwardIterator > equal_range(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <class ForwardIterator,   class LessThanComparable> thrust::pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value);
template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE thrust::pair< ForwardIterator, ForwardIterator > equal_range(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);
template <class ForwardIterator,   class T,   class StrictWeakOrdering> thrust::pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp);

Functions

Function lower_bound

template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE ForwardIterator lower_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the first position where value could be inserted without violating the ordering. This version of lower_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use lower_bound to search for values in a ordered range using the thrust::device execution policy for parallelization:

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::lower_bound(thrust::device, input.begin(), input.end(), 0); // returns input.begin()
thrust::lower_bound(thrust::device, input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::lower_bound(thrust::device, input.begin(), input.end(), 2); // returns input.begin() + 1
thrust::lower_bound(thrust::device, input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::lower_bound(thrust::device, input.begin(), input.end(), 8); // returns input.begin() + 4
thrust::lower_bound(thrust::device, input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: The furthermost iterator i, such that *i < value.

See:

Function lower_bound

template <class ForwardIterator,   class LessThanComparable> ForwardIterator lower_bound(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the first position where value could be inserted without violating the ordering. This version of lower_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), *j < value.

The following code snippet demonstrates how to use lower_bound to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::lower_bound(input.begin(), input.end(), 0); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: The furthermost iterator i, such that *i < value.

See:

Function lower_bound

template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE ForwardIterator lower_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the first position where value could be inserted without violating the ordering. This version of lower_bound uses function object comp for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use lower_bound to search for values in a ordered range using the thrust::device execution policy for parallelization:

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::lower_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • ForwardIterator is a model of Forward Iterator.
  • T is comparable to ForwardIterator'svalue_type.
  • StrictWeakOrdering is a model of Strict Weak Ordering.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: The furthermost iterator i, such that comp(*i, value) is true.

See:

Function lower_bound

template <class ForwardIterator,   class T,   class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); lower_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the first position where value could be inserted without violating the ordering. This version of lower_bound uses function object comp for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.

The following code snippet demonstrates how to use lower_bound to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::lower_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: The furthermost iterator i, such that comp(*i, value) is true.

See:

Function upper_bound

template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE ForwardIterator upper_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use upper_bound to search for values in a ordered range using the thrust::device execution policy for parallelism:

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::upper_bound(thrust::device, input.begin(), input.end(), 0); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 2); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 8); // returns input.end()
thrust::upper_bound(thrust::device, input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: The furthermost iterator i, such that value < *i is false.

See:

Function upper_bound

template <class ForwardIterator,   class LessThanComparable> ForwardIterator upper_bound(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.

The following code snippet demonstrates how to use upper_bound to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::upper_bound(input.begin(), input.end(), 0); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 2); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 8); // returns input.end()
thrust::upper_bound(input.begin(), input.end(), 9); // returns input.end()

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: The furthermost iterator i, such that value < *i is false.

See:

Function upper_bound

template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE ForwardIterator upper_bound(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses function object comp for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(value, *j) is false.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use upper_bound to search for values in a ordered range using the thrust::device execution policy for parallelization:

 #include <thrust/binary_search.h>
 #include <thrust/device_vector.h>
 #include <thrust/functional.h>
 #include <thrust/execution_policy.h>
 ...
 thrust::device_vector<int> input(5);

 input[0] = 0;
 input[1] = 2;
 input[2] = 5;
 input[3] = 7;
 input[4] = 8;

 thrust::upper_bound(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() +
1 thrust::upper_bound(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() +
1 thrust::upper_bound(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() +
2 thrust::upper_bound(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() +
2 thrust::upper_bound(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns input.end()
 thrust::upper_bound(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • ForwardIterator is a model of Forward Iterator.
  • T is comparable to ForwardIterator'svalue_type.
  • StrictWeakOrdering is a model of Strict Weak Ordering.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: The furthermost iterator i, such that comp(value, *i) is false.

See:

Function upper_bound

template <class ForwardIterator,   class T,   class StrictWeakOrdering> ForwardIterator upper_bound(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses function object comp for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(value, *j) is false.

The following code snippet demonstrates how to use upper_bound to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::upper_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.end()
thrust::upper_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: The furthermost iterator i, such that comp(value, *i) is false.

See:

template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE bool binary_search(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use binary_search to search for values in a ordered range using the thrust::device execution policy for parallelization:

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::binary_search(thrust::device, input.begin(), input.end(), 0); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 1); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 2); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 3); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 8); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 9); // returns false

Template Parameters:

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: true if an equivalent element exists in [first, last), otherwise false.

See:

template <class ForwardIterator,   class LessThanComparable> bool binary_search(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false.

The following code snippet demonstrates how to use binary_search to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::binary_search(input.begin(), input.end(), 0); // returns true
thrust::binary_search(input.begin(), input.end(), 1); // returns false
thrust::binary_search(input.begin(), input.end(), 2); // returns true
thrust::binary_search(input.begin(), input.end(), 3); // returns false
thrust::binary_search(input.begin(), input.end(), 8); // returns true
thrust::binary_search(input.begin(), input.end(), 9); // returns false

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: true if an equivalent element exists in [first, last), otherwise false.

See:

template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE bool binary_search(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use binary_search to search for values in a ordered range using the thrust::device execution policy for parallelization:

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
#include <thrust/execution_policy.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::binary_search(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns false

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • ForwardIterator is a model of Forward Iterator.
  • T is comparable to ForwardIterator'svalue_type.
  • StrictWeakOrdering is a model of Strict Weak Ordering.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: true if an equivalent element exists in [first, last), otherwise false.

See:

template <class ForwardIterator,   class T,   class StrictWeakOrdering> bool binary_search(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.

The following code snippet demonstrates how to use binary_search to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::binary_search(input.begin(), input.end(), 0, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 1, thrust::less<int>()); // returns false
thrust::binary_search(input.begin(), input.end(), 2, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 3, thrust::less<int>()); // returns false
thrust::binary_search(input.begin(), input.end(), 8, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 9, thrust::less<int>()); // returns false

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: true if an equivalent element exists in [first, last), otherwise false.

See:

Function equal_range

template <typename DerivedPolicy,   typename ForwardIterator,   typename LessThanComparable> _CCCL_HOST_DEVICE thrust::pair< ForwardIterator, ForwardIterator > equal_range(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j), where i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), *k < value. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), value < *k is false. For every iterator k in [i, j), neither value < *k nor *k < value is true.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use equal_range to search for values in a ordered range using the thrust::device execution policy for parallelization:

 #include <thrust/binary_search.h>
 #include <thrust/device_vector.h>
 #include <thrust/execution_policy.h>
 ...
 thrust::device_vector<int> input(5);

 input[0] = 0;
 input[1] = 2;
 input[2] = 5;
 input[3] = 7;
 input[4] = 8;

 thrust::equal_range(thrust::device, input.begin(), input.end(), 0); // returns [input.begin(), input.begin() + 1)
 thrust::equal_range(thrust::device, input.begin(), input.end(), 1); // returns [input.begin() + 1, input.begin() +
1) thrust::equal_range(thrust::device, input.begin(), input.end(), 2); // returns [input.begin() + 1, input.begin() +
2) thrust::equal_range(thrust::device, input.begin(), input.end(), 3); // returns [input.begin() + 2, input.begin() +
2) thrust::equal_range(thrust::device, input.begin(), input.end(), 8); // returns [input.begin() + 4, input.end)
 thrust::equal_range(thrust::device, input.begin(), input.end(), 9); // returns [input.end(), input.end)

Template Parameters:

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: A pair of iterators [i, j) that define the range of equivalent elements.

See:

Function equal_range

template <class ForwardIterator,   class LessThanComparable> thrust::pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first,   ForwardIterator last,   const LessThanComparable & value); equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j), where i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), *k < value. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), value < *k is false. For every iterator k in [i, j), neither value < *k nor *k < value is true.

The following code snippet demonstrates how to use equal_range to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
...
thrust::device_vector<int> input(5);

input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;

thrust::equal_range(input.begin(), input.end(), 0); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 1); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 2); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 3); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 8); // returns [input.begin() + 4, input.end)
thrust::equal_range(input.begin(), input.end(), 9); // returns [input.end(), input.end)

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.

Returns: A pair of iterators [i, j) that define the range of equivalent elements.

See:

Function equal_range

template <typename DerivedPolicy,   typename ForwardIterator,   typename T,   typename StrictWeakOrdering> _CCCL_HOST_DEVICE thrust::pair< ForwardIterator, ForwardIterator > equal_range(const thrust::detail::execution_policy_base< DerivedPolicy > & exec,   ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, last), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true.

The algorithm’s execution is parallelized as determined by exec.

The following code snippet demonstrates how to use equal_range to search for values in a ordered range using the thrust::device execution policy for parallelization:

 #include <thrust/binary_search.h>
 #include <thrust/device_vector.h>
 #include <thrust/functional.h>
 #include <thrust/execution_policy.h>
 ...
 thrust::device_vector<int> input(5);

 input[0] = 0;
 input[1] = 2;
 input[2] = 5;
 input[3] = 7;
 input[4] = 8;

 thrust::equal_range(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(),
input.begin() + 1) thrust::equal_range(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); //
returns [input.begin() + 1, input.begin() + 1) thrust::equal_range(thrust::device, input.begin(), input.end(), 2,
thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 2) thrust::equal_range(thrust::device,
input.begin(), input.end(), 3, thrust::less<int>()); // returns [input.begin() + 2, input.begin() + 2)
 thrust::equal_range(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns [input.begin() +
4, input.end) thrust::equal_range(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns
[input.end(), input.end)

Template Parameters:

  • DerivedPolicy The name of the derived execution policy.
  • ForwardIterator is a model of Forward Iterator.
  • T is comparable to ForwardIterator'svalue_type.
  • StrictWeakOrdering is a model of Strict Weak Ordering.

Function Parameters:

  • exec The execution policy to use for parallelization.
  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: A pair of iterators [i, j) that define the range of equivalent elements.

See:

Function equal_range

template <class ForwardIterator,   class T,   class StrictWeakOrdering> thrust::pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first,   ForwardIterator last,   const T & value,   StrictWeakOrdering comp); equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, last), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true.

The following code snippet demonstrates how to use equal_range to search for values in a ordered range.

 #include <thrust/binary_search.h>
 #include <thrust/device_vector.h>
 #include <thrust/functional.h>
 ...
 thrust::device_vector<int> input(5);

 input[0] = 0;
 input[1] = 2;
 input[2] = 5;
 input[3] = 7;
 input[4] = 8;

 thrust::equal_range(input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(), input.begin() +
1) thrust::equal_range(input.begin(), input.end(), 1, thrust::less<int>()); // returns [input.begin() + 1,
input.begin() + 1) thrust::equal_range(input.begin(), input.end(), 2, thrust::less<int>()); // returns [input.begin()
+ 1, input.begin() + 2) thrust::equal_range(input.begin(), input.end(), 3, thrust::less<int>()); // returns
[input.begin() + 2, input.begin() + 2) thrust::equal_range(input.begin(), input.end(), 8, thrust::less<int>()); //
returns [input.begin() + 4, input.end) thrust::equal_range(input.begin(), input.end(), 9, thrust::less<int>()); //
returns [input.end(), input.end)

Template Parameters:

Function Parameters:

  • first The beginning of the ordered sequence.
  • last The end of the ordered sequence.
  • value The value to be searched.
  • comp The comparison operator.

Returns: A pair of iterators [i, j) that define the range of equivalent elements.

See: