Monday, February 11, 2019

Interpolation Search Program in Java

In this post we’ll see how to write Interpolation search program in Java. Interpolation search is a variation of Binary search, meaning it is also a divide and conquer algorithm how it differs is that rather than dividing the input array into two equal parts it tries to divide the array in such a way that the position is nearer to the searched element.

How does Interpolation search work

One of the prerequisite for the Interpolation search is that the input array should be sorted and the values are uniformly distributed.

Interpolation search takes into account the lowest and highest elements in the array as well as length of the array and tries to estimate the position of the searched element. It works on the principle that the searched element is likely to be located near the end of the array if the searched element is close to the highest element in the array and it is likely to be located near the start of the array if the searched element is close to the lowest element in the array.

Interpolation search uses the following formula to calculate the position to be compared with the searched element.

position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] – arr[start]))

In each iteration searched element is compared with the element at the calculated position and start and end are adjusted based upon whether the searched element is greater than or less than the calculated position.

Interpolation search Java Program

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]));

      // Nearer to the highest element
      if (arr[position] < searchElement)
        start = position + 1;
      // Nearer to the lowest element
      else if (searchElement < arr[position])
        end = position - 1;
      else
        return position;
    }
    if (searchElement == arr[start])
      return start ;
    else
      return -1;
  }
}

Output for few of the searches-

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
55
Searched item 55 found at index 6

sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73]
Enter value to search: 
23
Searched item 23 found at index 4

Interpolation search Performance

Average case time complexity of Interpolation search is O(log(log(n))) if the elements are uniformly distributed. In worst case time complexity can be O(n).

Space complexity of Interpolation search is O(1) as no auxiliary space is required.

That's all for this topic Interpolation Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Exponential Search Program in Java
  2. Ternary Search Program in Java
  3. Shell Sort Program in Java
  4. Find Maximum And Minimum Numbers in a Given Matrix - Java Program
  5. Printing Numbers in Sequence Using Threads - Java Program

You may also like-

  1. Getting All The Tables in a Schema in a DB - Java Program
  2. Armstrong Number or Not Java Program
  3. Compressing And Decompressing File in GZIP Format - Java Program
  4. How to Create PDF From XML Using Apache FOP
  5. super Keyword in Java With Examples
  6. How ArrayList Works Internally in Java
  7. Phaser in Java Concurrency
  8. How to Inject Prototype Scoped Bean in Singleton Bean