Algoritma Interpolation Search

/**
 * Program  : Interpolation Search / pengembangan dari binary search
 * Date     : 12 Juli 2022
 * Author   : Riyanto
 * Website  : https://www.melonkoding.com
 */
 
class Main {
    
    static int[] dataset = {20, 30, 40, 60, 70, 75};
    
    public static void main(String[] args) {
        int dicari = 75;
        int hasil  = interpolation(dataset, dicari);
        
        if (hasil >= 0) System.out.println("Data ketemu pada posisi (index): "+ hasil);
        else System.out.println("Data tidak ditemukan");
    }
    
    
    public static int interpolation(int[] data, int item) {
        int low   = 0;
        int high  = data.length - 1;
        
        while ((data[low] <= item) && (data[high] >= item)) {
            int mid = ((item-data[low]) / (data[high] - data[low])) * (high - low) + low;
            
            if (data[mid] < item) {
                low = mid + 1;
            } else if(data[mid] > item){
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}