Question

Design and implement a program that implements an Interpolation Search method. Interpolation search is
similar to binary search, except it tries to begin the search nearer to the location of the item. Instead of the using the middle value of the sorted array, interpolation search estimates the location of the target with respect to the first & last values in the array. The implementation is the same as binary search except that you should calculate the mid value as:

mid = first + ((last - first) * (searchKey – arr[first])) / (arr[last] - arr[first])

Note that Interpolation Search will only work with numeric types! Your interpolation
search method should work on an array of integers

Language;java

Answer 1

// Java program to implement interpolation search

class Test
{
   // Array of items on which search will
   // be conducted.
   static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
                                       24, 33, 35, 42, 47};
  
   // If x is present in arr[0..n-1], then returns
   // index of it, else returns -1.
   static int interpolationSearch(int searchkey)
   {
       // Find indexes of two corners
       int first = 0, last = (arr.length - 1);
  
       // Since array is sorted, an element present
       // in array must be in range defined by corner
       while (first <= last && searchkey >= arr[first] && searchkey <= arr[last])
       {         

           if (first == last)
           {
               if (arr[first] == searchkey) return first;
               return -1;
           }
      
           // Probing the position with keeping
           // uniform distribution in mind.
          
           int pos = first + ((last-first)*(searchkey - arr[first])) /
               (arr[last]-arr[first]);
  
           // Condition of target found
           if (arr[pos] == searchkey)
               return pos;
  
           // If x is larger, x is in upper part
           if (arr[pos] < searchkey)
               first= pos + 1;
  
           // If x is smaller, x is in the lower part
           else
               last = pos - 1;
       }
       return -1;
   }
  
   // Driver method
   public static void main(String[] args)
   {
  
  
       int searchkey = 18; // Element to be searched
       int index = interpolationSearch(searchkey);
      
       // If element was found
       if (index != -1)
           System.out.println("Element found at index " + index);
           else
           System.out.println("Element not found.");
  
   }
}