◆ lower_bound() [3/8]

template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ ForwardIterator thrust::lower_bound ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 

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 function object comp for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), comp(*j, value) is true.

The algorithm's execution is parallelized as determined by exec.

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.
The furthermost iterator i, such that comp(*i, value) is true.
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 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(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
See also