Created
February 17, 2020 11:56
-
-
Save simonecid/4549bfa15a5ef5dc5a7cc128f990b656 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include <assert.h> | |
template<class TValue, int vecSize, int offset, int range> | |
class UpperBoundWrapper | |
{ | |
public: | |
static int binary_upper_bound(TValue values[vecSize], TValue x); | |
}; | |
template<class TValue, int vecSize, int offset> | |
class UpperBoundWrapper<TValue, vecSize, offset, 1> | |
{ | |
public: | |
static int binary_upper_bound(TValue values[vecSize], TValue x); | |
}; | |
template<class TValue, int vecSize, int offset, int range> | |
int UpperBoundWrapper<TValue, vecSize, offset, range>::binary_upper_bound(TValue values[vecSize], TValue x) | |
{ | |
constexpr int lMiddleElementIndex = offset + range / 2; | |
if (x >= values[lMiddleElementIndex]) | |
{ | |
return UpperBoundWrapper<TValue, vecSize, offset + range / 2, range / 2 + range % 2>::binary_upper_bound(values, x); | |
} | |
else | |
{ | |
return UpperBoundWrapper<TValue, vecSize, offset, range / 2>::binary_upper_bound(values, x); | |
} | |
} | |
template<class TValue, int vecSize, int offset> | |
int UpperBoundWrapper<TValue, vecSize, offset, 1>::binary_upper_bound(TValue values[vecSize], TValue x) | |
{ | |
return offset; | |
} | |
int main(int argc, char const *argv[]) | |
{ | |
int numbers[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90}; | |
for (int x = 0; x < 100; x++) | |
{ | |
int lUB = UpperBoundWrapper<int, 10, 0, 10>::binary_upper_bound(numbers, x); | |
std::cout << x << "'s upper bound is " << lUB << std::endl; | |
assert((x/10) == lUB); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment