Why does Interpolation Search if it is calculated manually then it only does 2 steps but when programmed it is more than 2 steps

Viewed 18

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!");
}
0 Answers
Related