It is an improved variant of the binary search.For this algorithm to apply data should be in sorted form.

There are scenarios where the target location is already known. For example, in case of telephone directory the word to be searched is already known and we need to go directly into the world we are searching.

If match occurs then index of item is returned. To split the list into two parts we use the following method −

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where 
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

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.

A  Array list
N  Size of A
X  Target Value

Procedure Interpolation_Search()

   Set Lo    0
   Set Mid  -1
   Set Hi    N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
 
   End While

End Procedure