Question

I'm writing a program in java that performs an interpolation search on an array of type double. I need a method that takes in that double array and a value to be searched for that is also of type double. I can find an implementation of the interpolation search that works with integer arrays but not with type double arrays. I need a method interpolationSearch(double[] arr, double searchValue) that returns the postion of where the value is if found and a -1 if not found in the array. I also need it to return the amount of steps it took to find the value using a counter everytime the interpolation search splits the array. Any help is appreciated and I will gladly give a thumbs up to correct answers!

Answer 1

class Main
{
public static int interpolation_search(double array[],double searchValue)
{
int n=array.length;
   int low = 0, high = (n - 1);
   while (low <= high && searchValue >= array[low] && searchValue <= array[high])
   {
       if (low == high)
       {
           if (array[low] == searchValue)
           return low;
           return -1;
       }
       int position = low + (int)(((double)(high - low) / (array[high] - array[low])) * (searchValue - array[low]));
       if (array[position] == searchValue)
           return position;
       if (array[position] < searchValue)
           low = position + 1;
       else
           high = position - 1;
   }
   return -1;
}
public static void main(String args[])
{
   double array[] = {10.4, 12.45, 13.67, 16.78, 18.99, 19.991, 20.670, 21.55,22.78, 23.70, 24.122, 33.234, 35.455, 42.67, 47.888};
   int n = array.length;
   double searchValue = 12.45;
   int index = interpolation_search(array,searchValue);
   if (index != -1)
       System.out.println("Element found at index "+index);
   else
       System.out.println("Element not found.");
}
}

OUTPUT:

Element found at index 1