thrust

◆ upper_bound() [3/8]

template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ ForwardIterator thrust::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.

Parameters
execThe execution policy to use for parallelization.
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
The furthermost iterator i, such that comp(value, *i) is false.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
ForwardIteratoris a model of Forward Iterator.
Tis comparable to ForwardIterator's value_type.
StrictWeakOrderingis a model of Strict Weak Ordering.

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:

...
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()
See also
http://www.sgi.com/tech/stl/upper_bound.html
lower_bound
equal_range
binary_search