thrust::lower_bound

Defined in thrust/binary_search.h

template<typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering> OutputIterator thrust::lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec, ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator result, StrictWeakOrdering comp)

lower_bound is a vectorized version of binary search: for each iterator v in [values_first, values_last) it attempts to find the value *v in an ordered range [first, last). Specifically, it returns the index of first position where value could be inserted without violating the ordering. This version of lower_bound uses function object comp for comparison.

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

The following code snippet demonstrates how to use lower_bound to search for multiple values in a ordered range.

#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::device_vector<int> values(6);
values[0] = 0;
values[1] = 1;
values[2] = 2;
values[3] = 3;
values[4] = 8;
values[5] = 9;

thrust::device_vector<unsigned int> output(6);

thrust::lower_bound(input.begin(), input.end(),
                    values.begin(), values.end(),
                    output.begin(),
                    thrust::less<int>());

// output is now [0, 1, 1, 2, 4, 5]

See also

upper_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.
values_first – The beginning of the search values sequence.
values_last – The end of the search values sequence.
result – The beginning of the output sequence.
comp – The comparison operator.

Template Parameters

DerivedPolicy – The name of the derived execution policy.
ForwardIterator – is a model of Forward Iterator.
InputIterator – is a model of Input Iterator. and InputIterator's value_type is comparable to ForwardIterator's value_type.
OutputIterator – is a model of Output Iterator. and ForwardIterator's difference_type is convertible to OutputIterator's value_type.
StrictWeakOrdering – is a model of Strict Weak Ordering.

Pre

The ranges [first,last) and [result, result + (last - first)) shall not overlap.