Interpolation Search

Interpolation Search is a search algorithm.

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. This search algorithm works on the probing position of the required value.

Interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

There are cases where the location of target data may be known in advance. For example, in case of a telephone directory, if we want to search the telephone number of Mohan. Here, linear search and even binary search will seem slow as we can directly jump to memory space where the names start from ‘M’ are stored.

Pseudocode

Step 1: Calculation of low and high values

Step 2: Check for the conditions :

(i) low <= high

(ii)a[low] <= value

(iii)a[high] >= value)

Do the below step 3 until any one of the above conditions fails.

Step 3.1: Calculate the value of mid

mid = Math.floor(low + ((high-low) * ((value-a[low])/(a[high]-a[low]))))

Step 3.2: If a[mid] matches with value, return the index of the item, and exit.

Step 3.3: If the value is less than a[mid], set the new high value to mid — 1.

Step 3.4: If the value is greater than a[mid], set the new low value to mid+ 1.

The code is executed until the condition is met, if the element is found then index of the element in array is returned else negative one is returned.

Below, I have shared my version of code in javascript.

The output for the above code is here below.

Code Walkthrough

array = [2,4,5,7,8,10,12,13,14,15,20,24]

search for value 20 in the above array using Interpolation searching algorithm.

On average the interpolation search makes about O(log(log(n))) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched.

Conclusion

Interpolation search finds a particular item by computing the probe position.

Feel free to check out for Linear and Binary Search algorithms here.