Template Function thrust::binary_search(ForwardIterator, ForwardIterator, InputIterator, InputIterator, OutputIterator, StrictWeakOrdering)¶

Function Documentation¶

template<class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering> OutputIterator thrust::binary_search(ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator result, StrictWeakOrdering comp)

binary_search 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). It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists. This version of binary_search uses function object comp for comparison.

The following code snippet demonstrates how to use

binary_search to search for multiple values in a ordered range.

Pre

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

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 LessThanComparable.
OutputIterator: is a model of Output Iterator. and bool is convertible to OutputIterator's value_type.
StrictWeakOrdering: is a model of Strict Weak Ordering.

#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<bool> output(6);

thrust::binary_search(input.begin(), input.end(),
                      values.begin(), values.end(),
                      output.begin(),
                      thrust::less<T>());

// output is now [true, false, true, false, true, false]

See: http://www.sgi.com/tech/stl/binary_search.html
See: lower_bound
See: upper_bound
See: equal_range