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__

**You may also like-**