Interpolation Search Algorithm – Time Complexity, Implementation in Java Vijay Sinha The Crazy Programmer
In this article we will have a look at an interesting Searching Algorithm: Interpolation Search. We will also look at some examples and the implementation. Along with this we look at complexity analysis of the algorithm and its advantage over other searching algorithms. Interpolation Search is a modified or rather an improved variant of Binary Search Algorithm. This algorithm works on probing position of the required value to search, the search tries to get close to the actual value at every step or until the search item is found. Now, Interpolation search requires works on arrays with conditions: The Array should be Sorted in ascending order. The elements in the Array should have Uniform distribution . In other words, the difference between two successive elements (Arr[i] – Arr[i+1]) in the array for each pair must be equal. Note: The second condition does not need to be true always. The given array cannot be fairly distributed sometimes. In that case, the probing index will