Vectorized Searches

Functions
template<class ForwardIterator , class InputIterator , class OutputIterator >
OutputIterator	thrust::lower_bound (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output)
template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >
OutputIterator	thrust::lower_bound (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output, StrictWeakOrdering comp)
template<class ForwardIterator , class InputIterator , class OutputIterator >
OutputIterator	thrust::upper_bound (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output)
template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >
OutputIterator	thrust::upper_bound (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output, StrictWeakOrdering comp)
template<class ForwardIterator , class InputIterator , class OutputIterator >
OutputIterator	thrust::binary_search (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output)
template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >
OutputIterator	thrust::binary_search (ForwardIterator first, ForwardIterator last, InputIterator values_first, InputIterator values_last, OutputIterator output, StrictWeakOrdering comp)

---

Function Documentation

template<class ForwardIterator , class InputIterator , class OutputIterator >

OutputIterator thrust::binary_search	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output
	)

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.

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.
output	The beginning of the output sequence.

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.

The following code snippet demonstrates how to use binary_search 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<bool> output(6);

  thrust::binary_search(input.begin(), input.end(),
                        values.begin(), values.end(),
                        output.begin());

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

See also:

http://www.sgi.com/tech/stl/binary_search.html

lower_bound

upper_bound

equal_range

template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >

OutputIterator thrust::binary_search	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output,
		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.

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

The following code snippet demonstrates how to use binary_search 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<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 also:

http://www.sgi.com/tech/stl/binary_search.html

lower_bound

upper_bound

equal_range

template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >

OutputIterator thrust::lower_bound	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output,
		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.

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

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

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

See also:

http://www.sgi.com/tech/stl/lower_bound.html

upper_bound

equal_range

binary_search

template<class ForwardIterator , class InputIterator , class OutputIterator >

OutputIterator thrust::lower_bound	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output
	)

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.

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.
output	The beginning of the output sequence.

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 ForwardIterator's difference_type is convertible to OutputIterator's value_type.

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:

http://www.sgi.com/tech/stl/lower_bound.html

upper_bound

equal_range

binary_search

template<class ForwardIterator , class InputIterator , class OutputIterator >

OutputIterator thrust::upper_bound	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output
	)

upper_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 last position where value could be inserted without violating the ordering.

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.
output	The beginning of the output sequence.

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 ForwardIterator's difference_type is convertible to OutputIterator's value_type.

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::upper_bound(input.begin(), input.end(),
                      values.begin(), values.end(),
                      output.begin());

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

See also:

http://www.sgi.com/tech/stl/upper_bound.html

upper_bound

equal_range

binary_search

template<class ForwardIterator , class InputIterator , class OutputIterator , class StrictWeakOrdering >

OutputIterator thrust::upper_bound	(	ForwardIterator	first,
		ForwardIterator	last,
		InputIterator	values_first,
		InputIterator	values_last,
		OutputIterator	output,
		StrictWeakOrdering	comp
	)

upper_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 upper_bound uses function object comp for comparison.

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

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::upper_bound(input.begin(), input.end(),
                      values.begin(), values.end(), 
                      output.begin(),
                      thrust::less<int>());

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

See also:

http://www.sgi.com/tech/stl/upper_bound.html

lower_bound

equal_range

binary_search