// Ichlalsul Bulqiah
// 190535646047
#include <iostream>
using namespace std;
int interpolationSearch(int *arr, int target, int topIdx, int bottomIdx = 0) {
if (bottomIdx <= topIdx && target >= arr[bottomIdx] && target <= arr[topIdx]) {
int pos = bottomIdx + ((target-arr[bottomIdx]) * ((topIdx-bottomIdx) / (arr[topIdx]-arr[bottomIdx])));
if (arr[pos] == target) {
return pos;
}
else if (arr[pos] < target) {
return interpolationSearch(arr, target, topIdx, pos+1);
}
else if (arr[pos] > target) {
return interpolationSearch(arr, target, pos-1, bottomIdx);
}
}
else {
return -1;
}
}
int main() {
int foo[] = {1, 3, 5, 7, 9, 11, 13, 15};
int arrLength = sizeof(foo)/sizeof(foo[0])-1;
int bar = interpolationSearch(foo, 5, arrLength);
cout << bar << endl;
return 0;
}
