Binary Search#
-
template<class Config = default_config, class HaystackIterator, class NeedlesIterator, class OutputIterator, class CompareFunction = ::rocprim::less<>>
inline hipError_t rocprim::binary_search(void *temporary_storage, size_t &storage_size, HaystackIterator haystack, NeedlesIterator needles, OutputIterator output, size_t haystack_size, size_t needles_size, CompareFunction compare_op = CompareFunction(), hipStream_t stream = 0, bool debug_synchronous = false)# Parallel primitive for performing a binary search (on a sorted range) of a given input.
The
binary_search
function determines for each element of a given input if it’s present in a given ordered rangehaystack
. It uses the search functiondetail::binary_search_op
which in turn uses a binary operatorcompare_op
for comparing the input values with the haystack ones.- Overview
When a null pointer is passed as
temporary_storage
, the required allocation size (in bytes) is written tostorage_size
and the function returns without performing the search operation.
- Example
In this example a device-level binary search on a haystack of integer values is performed on an input array of integer values too.
#include <rocprim/rocprim.hpp> // Prepare input and output (declare pointers, allocate device memory etc.). size_t haystack_size; // e.g. 10 int * haystack; // e.g. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} size_t needles_size; // e.g. 8 int * needles; // e.g. {0, 2, 12, 4, 14, 6, 8, 10} compare_op_type compare_op; // e.g. compare_op_type = rocprim::less<int> size_t * output; // empty array of needles_size elements // Get required size of the temporary storage. void * temporary_storage = nullptr; size_t temporary_storage_bytes; rocprim::binary_search<config>(temporary_storage, temporary_storage_bytes, haystack, needles, output, haystack_size, needles_size, compare_op, stream, debug_synchronous); // Allocate temporary storage. hipMalloc(&temporary_storage, temporary_storage_bytes); // Perform binary search. rocprim::binary_search<config>(temporary_storage, temporary_storage_bytes, haystack, needles, output, haystack_size, needles_size, compare_op, stream, debug_synchronous); // output = {1, 1, 0, 1, 0, 1, 1, 0}
- Template Parameters:
Config – - [optional] Configuration of the primitive. It can be
binary_search_config
or a class derived from it. Default isdefault_config
.HaystackIterator – - [inferred] Random-access iterator type of the search range. Must meet the requirements of a C++ InputIterator concept. It can be a simple pointer type.
NeedlesIterator – - [inferred] Random-access iterator type of the input range. Must meet the requirements of a C++ InputIterator concept. It can be a simple pointer type. Elements of the type pointed by it must be comparable to elements of the type pointed by
HaystackIterator
as either operand ofcompare_op
.OutputIterator – - [inferred] Random-access iterator type of the output range. Must meet the requirements of a C++ OutputIterator concept. It can be a simple pointer type.
CompareFunction – - [inferred] Type of binary function that accepts two arguments of the types pointed by
HaystackIterator
andNeedlesIterator
, and returns a value convertible to bool. Default type isrocprim::less<>
.
- Parameters:
temporary_storage – [in] - Pointer to a device-accessible temporary storage.
storage_size – [inout] - Reference to the size (in bytes) of
temporary_storage
.haystack – [in] - Iterator to the first element in the search range. Elements of this range must be sorted.
needles – [in] - Iterator to the first element in the range of values to search for on
haystack
.output – [out] - Iterator to the first element in the output range of boolean values.
haystack_size – [in] - Number of elements in the search range
haystack
.needles_size – [in] - Number of elements in the input range
needles
.compare_op – [in] - Binary operation function object that is used to compare values. The signature of the function should be equivalent to the following:
bool f(const T &a, const U &b);
. It does not need to haveconst &
, but the function object must not modify the objects passed to it. Default isCompareFunction()
.stream – [in] - [optional] HIP stream object. Default is
0
(default stream).debug_synchronous – [in] - [optional] If true, synchronization after every kernel launch is forced in order to check for errors.
- Returns:
hipSuccess
(0
) after a successful search; otherwise a HIP runtime error of typehipError_t
.