InterpolationSearch.java

// Java program to implement interpolation
public class InterpolationSearch {
    
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73};
    Arrays.sort(arr);
    System.out.println("sorted array- " + Arrays.toString(arr));
    System.out.println("Enter value to search: ");
    int searchElement = sc.nextInt();
    int index = interpolationSearch(arr, searchElement);
    if(index != -1){
      System.out.println("Searched item " + arr[index] + " found at index "+index);
    }else{
      System.out.println("Searched item " + searchElement + " not found in the array");
    }
    sc.close();
  }

  private static int interpolationSearch(int[] arr, int searchElement){
    int start = 0;
    int end = arr.length - 1;
    int position;
    while ((arr[end] != arr[start]) && (searchElement >= arr[start]) && (searchElement <= arr[end])) {
      position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] - arr[start]));

      if (arr[position] < searchElement)
        start = position + 1;
      else if (searchElement < arr[position])
        end = position - 1;
      else
        return position;
    }
    if (searchElement == arr[start])
      return start ;
    else
      return -1;
  }
}