thrust

◆ upper_bound() [4/8]

template<class ForwardIterator , class T , class StrictWeakOrdering >
ForwardIterator thrust::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.

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

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