Template Function thrust::upper_bound(ForwardIterator, ForwardIterator, const LessThanComparable&)

Function Documentation

template<class ForwardIterator, class LessThanComparable>
ForwardIterator thrust::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.
Return

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

Parameters

  • first: The beginning of the ordered sequence.

  • last: The end of the ordered sequence.

  • value: The value to be searched.

Template Parameters

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

See

http://www.sgi.com/tech/stl/upper_bound.html

See

lower_bound

See

equal_range

See

binary_search