public class MyClass {
private static int interpolation_search(int[] arr, int item) {
int low = 0;
int high = arr.length - 1;
int mid = -1;
int index = -1;
while (low <= high) {
mid = low + (((high - low) / (arr[high] - arr[low])) * (item - arr[low]));
if (arr[mid] == item) {
index = mid;
break;
}
else {
if (arr[mid] < item) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
}
return index;
}
public static void main(String args[]) {
int[] arr = {2, 5, 6, 8, 9, 12, 20, 34, 36, 40, 46, 51, 55, 61, 72, 86, 97};
int item = 51;
int index = interpolation_search(arr, item);
if (index != -1) {
System.out.print("index = " + index);
}
else {
System.out.print("Not found");
}
}
}
/*
run:
index = 11
*/
