I'm confused by the interpolation search calculation, the program provides different step results compared with manual calculations.
Input data: {3, 5, 10, 14, 21}
And I want to find the number 14. If calculated manually it only takes 2 steps to find 14.
I try this on my Interpolation Search program
System.out.println("post low higth " + post + " " + low + " " + hight);
And it shows 3 steps to find the key I'm looking for, as seen in the following picture.
But when I do
System.out.println("mid row col dataMid: " + mid + " " + left + " " + right);
in Binary Search, manual calculations and loops in the program are the same, which are only 2 steps, as seen in the following picture.
Can anyone explain me why this is happening?
This my interpolation search code
public static void interpolationSearch(int[] arr, int key){
int low,hight,post;
low = 0;
hight = arr.length-1;
while (low<=hight){
post = low+((key-arr[low])/(arr[hight]-arr[low]))*(hight-low);
System.out.println("post low higth " + post + " " + low + " " + hight);
if (key == arr[post]){
System.out.println("Data found");
System.out.println("data ada di indeks ke-: "+post);
return ;
}
else if (arr[post]>key){
hight = post-1;
}else {
low = post+1;
}
}
}
And this my binary search code
public static void binarySearch(int arr[], int key) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
System.out.println("mid left hight: " + mid + " " + left + " " + right);
//divide and conquer
if(key == arr[mid]) {
System.out.println("Data ditemukan!");
return;
} else if(key > arr[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println("Data tidak ditemukan!");
}