Interpolation search is an algorithm for searching a key in the array that has been ordered by numerical values assigned to the keys. Interpolation search is a type by which people search a telephone number for a name. The Interpolation Search is an improvement over the binary search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middlemost item of the collection. If a match occurs, then the index of the item is returned.

The below formula is used to calculate the mid-position in interpolation search.

mid = low + ((x – A[low]) * (high – low) / (A[high] – A[low]))

Algorithm:

Step 1 − Start searching data from middle of the list.

Step 2 − If it is a match, return the index of the item, and exit.

Step 3 − If it is not a match, probe position.

Step 4 − Divide the list using probing formula and find the new midle.

Step 5 − If data is greater than middle, search in higher sub-list.

Step 6 − If data is smaller than middle, search in lower sub-list.

Step 7 − Repeat until match.