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]))))