thrust::lower_bound

Defined in thrust/binary_search.h

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

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.

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 using the thrust::device execution policy for parallelization:

#include <thrust/binary_search.h>
#include <thrust/device_vector.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(thrust::device,
                    input.begin(), input.end(),
                    values.begin(), values.end(),
                    output.begin());

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

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 LessThanComparable.
OutputIterator – is a model of Output Iterator. and ForwardIterator's difference_type is convertible to OutputIterator's value_type.

Pre

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