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 range haystack. It uses the search function detail::binary_search_op which in turn uses a binary operator compare_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 to storage_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 is default_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 of compare_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 and NeedlesIterator, and returns a value convertible to bool. Default type is rocprim::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 have const &, but the function object must not modify the objects passed to it. Default is CompareFunction().

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