Fast Binary Search Template instead std::lower_bound for special cases

Revision en2, by dmkz, 2019-11-30 15:51:42

Hello everybody!

If you want to use binary search over array with known at compile time size, and this size can be extended to power of two, you can use next simple template:

template<int n, typename T>
int lowerBound(const T* __restrict arr, const T val) {
    if (n == 1) { return val > arr[0]; } 
    else {
        constexpr int mid = n / 2;
        if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
        else { return lowerBound<mid, T>(arr,val); }
    }
};

Testing on ideone shows, that it is faster in 4 times in comparison with std::lower_bound.

Thanks for reading this.

UPD. Testing for doubles, in 3.5 times faster.

Tags #binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English dmkz 2019-11-30 15:51:42 83
en1 English dmkz 2019-11-30 15:43:36 734 Initial revision (published)