thrust::upper_bound

Defined in thrust/binary_search.h

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

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

See also

lower_bound

See also

equal_range

See also

Binary Search

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.

Template Parameters

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

Returns

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