thrust
Modules | Functions
Binary Search

Modules

 

Functions

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)
 
template<class ForwardIterator , class LessThanComparable >
ForwardIterator thrust::lower_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
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)
 
template<class ForwardIterator , class T , class StrictWeakOrdering >
ForwardIterator thrust::lower_bound (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__ ForwardIterator thrust::upper_bound (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<class ForwardIterator , class LessThanComparable >
ForwardIterator thrust::upper_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ ForwardIterator thrust::upper_bound (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<class ForwardIterator , class T , class StrictWeakOrdering >
ForwardIterator thrust::upper_bound (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__ bool thrust::binary_search (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<class ForwardIterator , class LessThanComparable >
bool thrust::binary_search (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ bool thrust::binary_search (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<class ForwardIterator , class T , class StrictWeakOrdering >
bool thrust::binary_search (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__
thrust::pair< ForwardIterator,
ForwardIterator > 
thrust::equal_range (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<class ForwardIterator , class LessThanComparable >
thrust::pair< ForwardIterator,
ForwardIterator > 
thrust::equal_range (ForwardIterator first, ForwardIterator last, const LessThanComparable &value)
 
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__
thrust::pair< ForwardIterator,
ForwardIterator > 
thrust::equal_range (const thrust::detail::execution_policy_base< DerivedPolicy > &exec, ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 
template<class ForwardIterator , class T , class StrictWeakOrdering >
thrust::pair< ForwardIterator,
ForwardIterator > 
thrust::equal_range (ForwardIterator first, ForwardIterator last, const T &value, StrictWeakOrdering comp)
 

Detailed Description

Function Documentation

template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__ bool thrust::binary_search ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false.

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
true if an equivalent element exists in [first, last), otherwise false.
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 binary_search 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::binary_search(thrust::device, input.begin(), input.end(), 0); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 1); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 2); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 3); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 8); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 9); // returns false
See Also
http://www.sgi.com/tech/stl/binary_search.html
lower_bound
upper_bound
equal_range
template<class ForwardIterator , class LessThanComparable >
bool thrust::binary_search ( ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that *i < value and value < *i are both false.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
Returns
true if an equivalent element exists in [first, last), otherwise false.
Template Parameters
ForwardIteratoris a model of Forward Iterator.
LessThanComparableis a model of LessThanComparable.

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

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::binary_search(input.begin(), input.end(), 0); // returns true
thrust::binary_search(input.begin(), input.end(), 1); // returns false
thrust::binary_search(input.begin(), input.end(), 2); // returns true
thrust::binary_search(input.begin(), input.end(), 3); // returns false
thrust::binary_search(input.begin(), input.end(), 8); // returns true
thrust::binary_search(input.begin(), input.end(), 9); // returns false
See Also
http://www.sgi.com/tech/stl/binary_search.html
lower_bound
upper_bound
equal_range
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ bool thrust::binary_search ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.

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.
compThe comparison operator.
Returns
true if an equivalent element exists in [first, last), otherwise false.
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 binary_search 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::binary_search(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns false
thrust::binary_search(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns true
thrust::binary_search(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns false
See Also
http://www.sgi.com/tech/stl/binary_search.html
lower_bound
upper_bound
equal_range
template<class ForwardIterator , class T , class StrictWeakOrdering >
bool thrust::binary_search ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. Specifically, this version returns true if and only if there exists an iterator i in [first, last) such that comp(*i, value) and comp(value, *i) are both false.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
true if an equivalent element exists in [first, last), otherwise false.
Template Parameters
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 binary_search to search for values in a ordered range.

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::binary_search(input.begin(), input.end(), 0, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 1, thrust::less<int>()); // returns false
thrust::binary_search(input.begin(), input.end(), 2, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 3, thrust::less<int>()); // returns false
thrust::binary_search(input.begin(), input.end(), 8, thrust::less<int>()); // returns true
thrust::binary_search(input.begin(), input.end(), 9, thrust::less<int>()); // returns false
See Also
http://www.sgi.com/tech/stl/binary_search.html
lower_bound
upper_bound
equal_range
template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__ thrust::pair<ForwardIterator, ForwardIterator> thrust::equal_range ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j), where i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), *k < value. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), value < *k is false. For every iterator k in [i, j), neither value < *k nor *k < value is true.

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
A pair of iterators [i, j) that define the range of equivalent elements.
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 equal_range 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::equal_range(thrust::device, input.begin(), input.end(), 0); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 1); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 2); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 3); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 8); // returns [input.begin() + 4, input.end)
thrust::equal_range(thrust::device, input.begin(), input.end(), 9); // returns [input.end(), input.end)
See Also
http://www.sgi.com/tech/stl/equal_range.html
lower_bound
upper_bound
binary_search
template<class ForwardIterator , class LessThanComparable >
thrust::pair<ForwardIterator, ForwardIterator> thrust::equal_range ( ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j), where i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), *k < value. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, j), value < *k is false. For every iterator k in [i, j), neither value < *k nor *k < value is true.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
Returns
A pair of iterators [i, j) that define the range of equivalent elements.
Template Parameters
ForwardIteratoris a model of Forward Iterator.
LessThanComparableis a model of LessThanComparable.

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

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::equal_range(input.begin(), input.end(), 0); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 1); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 2); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 3); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 8); // returns [input.begin() + 4, input.end)
thrust::equal_range(input.begin(), input.end(), 9); // returns [input.end(), input.end)
See Also
http://www.sgi.com/tech/stl/equal_range.html
lower_bound
upper_bound
binary_search
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ thrust::pair<ForwardIterator, ForwardIterator> thrust::equal_range ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, last), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true.

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.
compThe comparison operator.
Returns
A pair of iterators [i, j) that define the range of equivalent elements.
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 equal_range 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::equal_range(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns [input.begin() + 4, input.end)
thrust::equal_range(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns [input.end(), input.end)
See Also
http://www.sgi.com/tech/stl/equal_range.html
lower_bound
upper_bound
binary_search
template<class ForwardIterator , class T , class StrictWeakOrdering >
thrust::pair<ForwardIterator, ForwardIterator> thrust::equal_range ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

equal_range is a version of binary search: it attempts to find the element value in an ordered range [first, last). The value returned by equal_range is essentially a combination of the values returned by lower_bound and upper_bound: it returns a pair of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [first, last) that has this property.

This version of equal_range returns a pair of iterators [i, j). i is the furthermost iterator in [first, last) such that, for every iterator k in [first, i), comp(*k, value) is true. j is the furthermost iterator in [first, last) such that, for every iterator k in [first, last), comp(value, *k) is false. For every iterator k in [i, j), neither comp(value, *k) nor comp(*k, value) is true.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
A pair of iterators [i, j) that define the range of equivalent elements.
Template Parameters
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 equal_range to search for values in a ordered range.

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::equal_range(input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(), input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 1, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 1)
thrust::equal_range(input.begin(), input.end(), 2, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 3, thrust::less<int>()); // returns [input.begin() + 2, input.begin() + 2)
thrust::equal_range(input.begin(), input.end(), 8, thrust::less<int>()); // returns [input.begin() + 4, input.end)
thrust::equal_range(input.begin(), input.end(), 9, thrust::less<int>()); // returns [input.end(), input.end)
See Also
http://www.sgi.com/tech/stl/equal_range.html
lower_bound
upper_bound
binary_search
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
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.

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

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

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.
compThe comparison operator.
Returns
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
http://www.sgi.com/tech/stl/lower_bound.html
upper_bound
equal_range
binary_search
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.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
The furthermost iterator i, such that comp(*i, value) is true.
Template Parameters
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.

...
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
http://www.sgi.com/tech/stl/lower_bound.html
upper_bound
equal_range
binary_search
template<typename DerivedPolicy , typename ForwardIterator , typename LessThanComparable >
__host__ __device__ ForwardIterator thrust::upper_bound ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.

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 value < *i is false.
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 upper_bound to search for values in a ordered range using the thrust::device execution policy for parallelism:

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::upper_bound(thrust::device, input.begin(), input.end(), 0); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 2); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 8); // returns input.end()
thrust::upper_bound(thrust::device, input.begin(), input.end(), 9); // returns input.end()
See Also
http://www.sgi.com/tech/stl/upper_bound.html
lower_bound
equal_range
binary_search
template<class ForwardIterator , class LessThanComparable >
ForwardIterator thrust::upper_bound ( ForwardIterator  first,
ForwardIterator  last,
const LessThanComparable &  value 
)

upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_bound uses operator< for comparison and returns the furthermost iterator i in [first, last) such that, for every iterator j in [first, i), value < *j is false.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
Returns
The furthermost iterator i, such that value < *i is false.
Template Parameters
ForwardIteratoris a model of Forward Iterator.
LessThanComparableis a model of LessThanComparable.

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

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::upper_bound(input.begin(), input.end(), 0); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 2); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 8); // returns input.end()
thrust::upper_bound(input.begin(), input.end(), 9); // returns input.end()
See Also
http://www.sgi.com/tech/stl/upper_bound.html
lower_bound
equal_range
binary_search
template<typename DerivedPolicy , typename ForwardIterator , typename T , typename StrictWeakOrdering >
__host__ __device__ ForwardIterator thrust::upper_bound ( const thrust::detail::execution_policy_base< DerivedPolicy > &  exec,
ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_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(value, *j) is false.

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.
compThe comparison operator.
Returns
The furthermost iterator i, such that comp(value, *i) is false.
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 upper_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::upper_bound(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns input.end()
thrust::upper_bound(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
See Also
http://www.sgi.com/tech/stl/upper_bound.html
lower_bound
equal_range
binary_search
template<class ForwardIterator , class T , class StrictWeakOrdering >
ForwardIterator thrust::upper_bound ( ForwardIterator  first,
ForwardIterator  last,
const T &  value,
StrictWeakOrdering  comp 
)

upper_bound is a version of binary search: it attempts to find the element value in an ordered range [first, last). Specifically, it returns the last position where value could be inserted without violating the ordering. This version of upper_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(value, *j) is false.

Parameters
firstThe beginning of the ordered sequence.
lastThe end of the ordered sequence.
valueThe value to be searched.
compThe comparison operator.
Returns
The furthermost iterator i, such that comp(value, *i) is false.
Template Parameters
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 upper_bound to search for values in a ordered range.

...
thrust::device_vector<int> input(5);
input[0] = 0;
input[1] = 2;
input[2] = 5;
input[3] = 7;
input[4] = 8;
thrust::upper_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
thrust::upper_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
thrust::upper_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.end()
thrust::upper_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
See Also
http://www.sgi.com/tech/stl/upper_bound.html
lower_bound
equal_range
binary_search