thrust::lower_bound#

Overloads#

lower_bound(exec, first, last, value)#

template<typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
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.

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:

#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::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

https://en.cppreference.com/w/cpp/algorithm/lower_bound

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.

  • value – The value to be searched.

Template Parameters:

  • DerivedPolicy – The name of the derived execution policy.

  • ForwardIterator – is a model of Forward Iterator.

  • LessThanComparable – is a model of LessThanComparable.

Returns:

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

lower_bound(first, last, value)#

template<class ForwardIterator, class LessThanComparable>
ForwardIterator thrust::lower_bound(
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 following code snippet demonstrates how to use lower_bound to search for values in a ordered range.

#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::lower_bound(input.begin(), input.end(), 0); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9); // returns input.end()

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

See also

upper_bound

See also

equal_range

See also

binary_search

Parameters:

  • first – The beginning of the ordered sequence.

  • last – The end of the ordered sequence.

  • value – The value to be searched.

Template Parameters:
Returns:

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

lower_bound(exec, first, last, value, comp)#

template<typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
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.

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:

#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::lower_bound(input.begin(), input.end(), 0, ::cuda::std::less<int>()); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1, ::cuda::std::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2, ::cuda::std::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3, ::cuda::std::less<int>()); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8, ::cuda::std::less<int>()); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9, ::cuda::std::less<int>()); // returns input.end()

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

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.

  • value – The value to be searched.

  • comp – The comparison operator.

Template Parameters:

  • DerivedPolicy – The name of the derived execution policy.

  • ForwardIterator – is a model of Forward Iterator.

  • T – is comparable to ForwardIterator's value_type.

  • StrictWeakOrdering – is a model of Strict Weak Ordering.

Returns:

The furthermost iterator i, such that comp(*i, value) is true.

lower_bound(first, last, value, comp)#

template<class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator thrust::lower_bound(
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 following code snippet demonstrates how to use lower_bound to search for values in a ordered range.

#include <thrust/binary_search.h>
#include <thrust/device_vector.h>
#include <thrust/functional.h>
...
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, ::cuda::std::less<int>()); // returns input.begin()
thrust::lower_bound(input.begin(), input.end(), 1, ::cuda::std::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 2, ::cuda::std::less<int>()); // returns input.begin() + 1
thrust::lower_bound(input.begin(), input.end(), 3, ::cuda::std::less<int>()); // returns input.begin() + 2
thrust::lower_bound(input.begin(), input.end(), 8, ::cuda::std::less<int>()); // returns input.begin() + 4
thrust::lower_bound(input.begin(), input.end(), 9, ::cuda::std::less<int>()); // returns input.end()

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

See also

upper_bound

See also

equal_range

See also

binary_search

Parameters:

  • first – The beginning of the ordered sequence.

  • last – The end of the ordered sequence.

  • value – The value to be searched.

  • comp – The comparison operator.

Template Parameters:
Returns:

The furthermost iterator i, such that comp(*i, value) is true.

lower_bound(exec, first, last, values_first, values_last, result)#

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

https://en.cppreference.com/w/cpp/algorithm/lower_bound

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.

lower_bound(first, last, values_first, values_last, result)#

template<class ForwardIterator, class InputIterator, class OutputIterator>
OutputIterator thrust::lower_bound(
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 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>
...
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());

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

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

See also

upper_bound

See also

equal_range

See also

binary_search

Parameters:

  • 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:
Pre:

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

lower_bound(exec, first, last, values_first, values_last, result, comp)#

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(),
                    ::cuda::std::less<int>());

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

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

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.

lower_bound(first, last, values_first, values_last, result, comp)#

template<class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
OutputIterator thrust::lower_bound(
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 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>
...
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(),
                    ::cuda::std::less<int>());

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

See also

https://en.cppreference.com/w/cpp/algorithm/lower_bound

See also

upper_bound

See also

equal_range

See also

binary_search

Parameters:

  • 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:

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