Skip to content

Draft: Proposed enhancement for binary_search_leftmost

Valentin Kotolup requested to merge vkotolup_bin_search_improvements into master

This merge request explores the potential of integrating a hybrid search algorithm, which combines elements of binary and interpolation search, into the search by triplet function currently utilizing the binary_search_leftmost method from BinarySearch.cuh.

The proposed modification is specifically optimized for GPU environments and is not expected to yield significant benefits when deployed on CPUs.

The incentive for this proposal is rooted in the average performance of binary search being log(n), while interpolation search performs at log(log(n)). The underlying assumption is that this could potentially decrease the number of requests made to global memory.

Merge request reports