In this post, we will learn How to Implement the Interpolation search program in Java. Interpolation search is an algorithm which tries to improve the Binary search, I mean to say that it also follows the divide and conquer algorithm like binary search but how it differs is that rather than dividing the input array into two equal parts it basically tries to divide the array in such a way that the position is nearer to the searched element.
How Interpolation search for work?
One of the prerequisites of the Interpolation search is that the input array should be sorted and the values are uniformly distributed.
Interpolation search takes the lowest and highest elements into account in the array as well as the length of the array and tries to estimate the position of the searched element.
This algorithm usually 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.
Or 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 usually using the below formula to calculate the position to be compared with the searched element key.
position = start + ((searchKey – arr[start]) * (end – start) / (arr[end] – arr[start]))
In each iteration searching 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.
The average time complexity of Interpolation search is O(log(log(n))) if all elements are uniformly distributed. The worst-case time complexity can be O(n).
The space complexity of the Interpolation search is O(1) as Single auxiliary space is required to hold a position variable.
Below is the Complete Source code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
package com.kkjavatutorials.client; import java.util.Arrays; import java.util.Scanner; /** * Client Program for interpolation Search in Java * * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { Scanner scanner = null; try { scanner = new Scanner(System.in); //Input Array int[] inputArr = { 100, 30, 67, 24, 56, 70, 80, 9, 45 }; /*Sort this input array to fulfill interpolation prerequisites*/ Arrays.sort(inputArr); //Printing Sorted input Array.. System.out.println("Sorted array- " + Arrays.toString(inputArr)); //Ask to user to enter search key System.out.println("Enter value to be searched: "); int searchKey = scanner.nextInt(); int result = performInterpolationSearch(inputArr, searchKey); if (result != -1) { System.out.println("SearchKey " + inputArr[result] + " found at index " + result); } else { System.out.println("SearchKey " + searchKey + " not found!"); } } catch (Exception e) { e.printStackTrace(); }finally { if(scanner != null) scanner.close(); } } /** * Funtcion to perform an interpolation Search * @param inputArr input array * @param searchKey element to be searched * @return if seachKey found then return * index of seachKey else -1 */ private static int performInterpolationSearch(int[] inputArr, int searchKey) { int start = 0; int end = inputArr.length - 1; int position; while ((inputArr[end] != inputArr[start]) && (searchKey >= inputArr[start]) && (searchKey <= inputArr[end])) { position = start + ((searchKey - inputArr[start]) * (end - start) / (inputArr[end] - inputArr[start])); // If searchKey is near to the highest element if (inputArr[position] < searchKey) start = position + 1; // if searchKey is near to the lowest element else if (searchKey < inputArr[position]) end = position - 1; else //if searchKey is at position index return position; } //if searchKey is at start index if (searchKey == inputArr[start]) return start; else //if searchKey is not found return -1; } } |
The Some input/output of this program:
Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
56
SearchKey 56 found at index 4
Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
80
SearchKey 80 found at index 7
Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
34
SearchKey 34 not found!
You May Also Like:
Java program for linear search using the Iterative Approach
Java program for linear search using Recursive Approach
Java program for Binary search using Iterative Approach
Java program for binary search using the Recursive Approach
That’s all about Interpolation Search Program in Java
If you have any feedback or suggestion please feel free to drop in below comment box.