Template Function ADS::gallopSearch

• Defined in File BinarySearch.h

Function Documentation

template<class T, class C = std::less<>>
std::size_t ADS::gallopSearch(const std::vector<T> &A, const T &v, C less = C())

the first place h of an item not smaller than v, found by looking at the places 0 , 1 , 3 , 7 , … and then by a binary search, O( log h )

Pre:

A is sorted

Post:

A[ r - 1 ] < v <= A[ r ]