Question

Language: Java

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

Answer 1

import java.util.Scanner;
import java.util.Arrays;
public class Main
{
public static int interpolationSearch(int arr[], int n, int key)
{
  
int low = 0, high = (n - 1);
while (low <= high && key >= arr[low] && key <= arr[high])

{
if (low == high)
{
  
if (arr[low] == key) return low;
return -1;
  

  
}
  
int position = low + (((high-low) / (arr[high]-arr[low]))*(key - arr[low]));

if (arr[position] == key)
{
return position;
}

else if (arr[position] < key)
{
low = position + 1;
}

else if(arr[position] > key)
{
high = position - 1;
}
}
  
return -1;
}
public static void main( String[] args)
{
  
Scanner scan = new Scanner(System.in);
int a[] = new int[100];
  
System.out.println("Enter number of elements :");
  
int n = scan.nextInt();
  
int i,index;
  
for(i=0;i<n;i++)
{
a[i] = scan.nextInt();
}
  
System.out.println("Enter key to be search :");

int key = scan.nextInt();
  
Arrays.sort(a,0,n-1);
index=interpolationSearch(a,n,key);
  
if(index!=-1)
{
System.out.println("Element is present in array at"+index);
}
  
else
System.out.println("Element is not present in array");
}
}