Upper and lower bounds of arrays

upper-lower-bounds

#include <cstdio>


template <class T>
int upper_bound(const T array[], T element, size_t left_index, size_t right_index)
{
	int result = -1;

	printf("upper: at start left_index: %lu\n", left_index);
	printf("upper: at start right_index: %lu\n",right_index);

	while (left_index < right_index)
	{	
		// 1. Select middle element 
		size_t middle_index = left_index + (right_index - left_index) / 2;

		// upper bound -->
		if (array[middle_index] > element)
			right_index = middle_index;
		else
			left_index = middle_index + 1; // we keep in middle in range because it can be equal or more 
									   // this in fact makes it upper bound finder ...
	}

	printf("upper: left_index: %lu\n", left_index);
	printf("upper: right_index: %lu\n", right_index);

	return right_index - 1;
}

template <class T>
int lower_bound(const T array[], T element, size_t left_index, size_t right_index)
{
	int result = -1;

	printf("lower: at start left_index: %lu\n", left_index);
	printf("lower: at start right_index: %lu\n",right_index);

	while (left_index < right_index)
	{	
		// 1. Select middle element 
		size_t middle_index = left_index + (right_index - left_index) / 2;

		// lower bound --> 
		if (array[middle_index] < element)
			left_index = middle_index + 1;
		else 
			right_index = middle_index;
	}

	printf("lower: left_index: %lu\n", left_index);
	printf("lower: right_index: %lu\n", right_index);

	return left_index;
}

int main()
{
	static const int a[] = {1, 1, 2,2,2,2,2,3, 4, 4, 4, 4, 4, 5,6};

	int index = 0;

	index = lower_bound<int>(a, 2, 0, sizeof(a) / sizeof(int));
		printf("lb: %d\n", index);
	index = upper_bound<int>(a, 2, 0, sizeof(a) / sizeof(int));
		printf("ub: %d\n", index);

	printf("\n");
	index = lower_bound<int>(a, 4, 0, sizeof(a) / sizeof(int));
		printf("lb: %d\n", index);
	index = upper_bound<int>(a, 4, 0, sizeof(a) / sizeof(int));	
		printf("ub: %d\n", index);
}