Interpolation Search Algorithm in Java

This is a Java Program to Implement Interpolation Search Algorithm. Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons.
In interpolation-sequential search, interpolation is used to find an item near the one being searched for, then linear search is used to find the exact item.

Here is the source code of the Java Program to Implement Interpolation Search Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Interpolation Search Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class InterpolationSearch **/
  8. public class InterpolationSearch
  9. {
  10.     /** interpolationSearch function **/
  11.     public static int interpolationSearch(int[] sortedArray, int toFind)
  12.     {
  13.         int low = 0;
  14.         int high = sortedArray.length - 1;
  15.         int mid;
  16.         while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) 
  17.         {
  18.             if (sortedArray[high] - sortedArray[low] == 0)
  19.                 return (low + high)/2;
  20.             /** out of range is possible  here **/
  21.              mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);  
  22.  
  23.              if (sortedArray[mid] < toFind)
  24.                  low = mid + 1;
  25.              else if (sortedArray[mid] > toFind)
  26.                  high = mid - 1;
  27.              else
  28.                  return mid;
  29.         }
  30.         if (sortedArray[low] == toFind)
  31.             return low;
  32.            /** not found **/
  33.         else
  34.             return -1; 
  35.     }    
  36.     /** Main method **/
  37.     public static void main(String[] args) 
  38.     {
  39.         Scanner scan = new Scanner( System.in );        
  40.         System.out.println("Interpolation Search Test\n");
  41.         int n, i;
  42.         /** Accept number of elements **/
  43.         System.out.println("Enter number of integer elements");
  44.         n = scan.nextInt();
  45.         /** Create integer array on n elements **/
  46.         int arr[] = new int[ n ];
  47.         /** Accept elements **/
  48.         System.out.println("\nEnter "+ n +" sorted integer elements");
  49.         for (i = 0; i < n; i++)
  50.             arr[i] = scan.nextInt();
  51.         System.out.println("\nEnter element to search for : ");
  52.         int key = scan.nextInt();
  53.  
  54.         int result = interpolationSearch(arr, key);
  55.  
  56.         if (result == -1)
  57.             System.out.println("\n"+ key +" element not found");
  58.         else
  59.             System.out.println("\n"+ key +" elemnt found at position "+ result);
  60.  
  61.     }    
  62. }

Interpolation Search Test
 
Enter number of integer elements
10
 
Enter 10 sorted integer elements
12 24 36 48 60 72 84 96 108 120
 
Enter element to search for :
24
 
24 elemnt found at position 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.