Template_upper_bound.cpp

#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;
}