Skip to content

Instantly share code, notes, and snippets.

@farnasirim
Last active December 8, 2019 17:05
Show Gist options
  • Save farnasirim/165c4ca98b108cee44448656cd8ee620 to your computer and use it in GitHub Desktop.
Save farnasirim/165c4ca98b108cee44448656cd8ee620 to your computer and use it in GitHub Desktop.
Ternary search on integer domain + test drive
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment