#include<stdio.h>
int interpolationsearch(int array[],int n,int key){
int low = 0;
int high = n;
while(low <= high && key >= array[low] && key <= array[high]){
int position = low + ((high - low) * (key - array[low]) / (array[high] - array[low]));
if(array[position] == key){
return position + 1;
}else if(array[position] > key){
high = position - 1;
}else{
low = position + 1;
}
}
return -1;
}
int main(){
int array[] = {12,13,27,38,39,44,58,62};
int key = 13;
int position = interpolationsearch(array,8,key);
if(position == -1){
printf("Not Found");
}else{
printf("Found On %d",position);
}
return 0;
}