Ternary search on integer domain + test drive

ternary_on_integer_domain.cpp

#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

template <typename Compare>
int findMax(int from, int to, Compare lessFunctor) { // from and to are inclusive: [from, to]
	pair<int, int> origFromTo;
	while(to - from > 3) {
		origFromTo = make_pair(from, to);

		int oneThird = from + (to - from)/3;
		int twoThirds = from + (2*(to - from))/3;

		
		if(lessFunctor(oneThird, twoThirds)) {
			from = oneThird;
		} else {
			to = twoThirds;
		}
	}
	
	auto retIndex = from;
	for(int i = from + 1; i <= to; i++) {
		if(lessFunctor(retIndex, i)) {
			retIndex = i;
		}
	}

	return retIndex;
}

template <typename T, class Compare>
struct VectorComparator {
	const vector<T>& internalArray;
	Compare cmp;

	VectorComparator(const vector<T>& origArray, Compare cmp): internalArray(origArray), cmp(cmp) {
	}

	bool operator()(int i, int j) { // less
		return cmp(internalArray[i], internalArray[j]);
	}
};


template<typename T>
vector<T> generateBitonicArray(int sz, int maxIndex);

template<>
vector<double> generateBitonicArray<double>(int sz, int maxIndex) {
	vector<double> arr;

	double first = ((double)rand() + 1) / RAND_MAX;
	arr.push_back(first);

	while(arr.size()-1 != maxIndex) {
		arr.push_back(arr.back() + ((double)rand() + 1) / RAND_MAX);
	}

	while(arr.size() < sz) {
		arr.push_back(arr.back() - ((double)rand() + 1) / RAND_MAX);
	}

	return arr;
}


template<typename T>
void testDriveSingle(const vector<T>& bitonicArray, int ans) {
	auto ctor = VectorComparator<T, less<T>>(bitonicArray, less<T>());
	auto idx = findMax(0, bitonicArray.size() - 1, ctor);

	if(ans != idx) {
		for(auto it: bitonicArray) {
			cout << it << " ";
		}
		cout << endl;
		cout << "exp : " << ans << endl;
		cout << "act : " << idx << endl;
	}

	assert(ans == idx);
}

template<typename T>
void testDrive(int arraySize, int testCases) {
	vector<int> positionsOfAns = {0, arraySize - 1};
	for(int i = 0; i < testCases; i++) {
		positionsOfAns.push_back(rand()%arraySize);
	}

	for(auto ansIndex: positionsOfAns) {
		testDriveSingle(generateBitonicArray<T>(arraySize, ansIndex), ansIndex);
	}
}

int main() {
	srand(1231231231);

	for(int arraySize = 1; arraySize <= 200; arraySize++) {
		testDrive<double>(arraySize, arraySize*2);
	}
	cout << "pass" << endl;
	
	return 0;
}