Interpolation Search

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