thrust

◆ lower_bound() [1/8]

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

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.
Returns
The furthermost iterator i, such that *i < value.
Template Parameters
DerivedPolicyThe name of the derived execution policy.
ForwardIteratoris a model of Forward Iterator.
LessThanComparableis a model of LessThanComparable.

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:

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

Referenced by thrust::mr::disjoint_unsynchronized_pool_resource< Upstream, Bookkeeper >::do_allocate(), and thrust::mr::disjoint_unsynchronized_pool_resource< Upstream, Bookkeeper >::do_deallocate().