gistfile1.txt

#include <iostream>
#include <cmath>
using namespace std;

int z = 0;

int interpolation(int arr[], int left, int right, int key){

    int low = left;
    int high = right - 1;
    int mid;

    while (arr[high] != arr[low] && key >= arr[low] && key <= arr[high]) {

        mid = low + ( (key - arr[low]) * (high - low) / (arr[high] - arr[low]) );

        if (key > arr[mid]){

            low = mid + 1;

        } else if (key < arr[mid]){

            high = mid - 1;

        } else{

            return mid;

        }

    }

    if (key == arr[low]){

        return low ;

    } else {

        return -1;

    }

}

int main()
{

    int L[] = {0, 1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    //int L[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int left = 0;
    int right = sizeof(L) / sizeof(L[0]);

    int key = 144;

    int x;
    if((x = interpolation(L, left, right, key)) == -1 ){

        cout << "Key doesn't exist"<< endl;

    } else {

        cout << "The position of Key is " << x << endl;

    }

return 0; }