Interpolation Search in Java

Time complexity plays a major role in competitive programming problems. To get rid of TLE  we try different approaches and look for the best algorithm on basis of time complexity.

Now, coming to search algorithm, linear search is the easiest algorithm but not works when the size of the array is large as it takes O(n) comparison. Binary Search is a modification over linear search which works for sorted array and check on basis of middle element repeatedly. It takes O(log n ) comparisons.

Interpolation Search in Java

Modification of Binary Search is Interpolation Search which goes to an appropriate location according to the value of key to be searched. It takes O ( log log n ) comparisons.

So, in this Java tutorial, we are going to discuss the implementation of Interpolation Search.

Interpolation Search Vs Binary Search

Interpolation search works better than Binary Search. Binary search always checks on a middle element basis, but interpolation search may go to different locations according to the value of key to be searched.

Binary search takes O ( log n ) comparisons to search for a key in sorted array but interpolation search takes O ( log log n ) comparisons.

An algorithm of Interpolation Search

1. Sort the given array.
2. Declare the variables low =0 and high = array_size-1 .
3. Now, check if there is only 1 element in array by checking low==high is true if there is the only element in array. If there is only one element check it with the key value if equals to it return 1 otherwise -1.
4. Otherwise , using formula
   int position = low + (((high-low) / (a[high]-a[low]))*(key – a[low]));  (check for the appropriate position of key value in array.)
5. if our key value is equal to value of array element at index (position) return 1 if the key value is greater than update low to position+1 if the key is smaller than update high to position-1.
6. Repeat the algorithm until the key is not found and low<=high.

Java code to implement Interpolation Search

 
import java.util.Scanner;

import java.util.Arrays;


  public class Codespeedy
{
   public static int interpolation_Search(int a[], int n, int key) 
 { 
  
  int low = 0, high = (n - 1); 


  while (low <= high && key >= a[low] && key <= a[high]) 
 
   { 
      if (low == high) 
     { 
        
      if (a[high] == key)
        return 1; 
    
       	else
         return -1;
      
     } 
    
    int position = low + (((high-low) / (a[high]-a[low]))*(key - a[low])); 

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

     
    else if(a[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;
        
          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);
        
     if(interpolation_Search(a,n,key)!=-1)
   {
          System.out.println("Element is present in array");
   }
      
      else
        System.out.println("Element is not present in array");
  } 

}

INPUT

Enter number of elements : 5
1 2 3 4 5
Enter key to be search : 4

OUTPUT

The element is present in array.

Time Complexity

When elements are uniformly distributed, then O ( log log n ) . In worst case, it can take upto O ( n).

Learn more,

• Check whether a given tree is a Binary Search Tree in Java
• How to Count leaf nodes in a binary tree using Recursion in Java