Data Structure & Algorithm: Interpolation Search

    Interpolation search is a searching algorithm that applies to a sorted & equally distributed array, and it is an Improved variant of Binary Search . Like binary search, it uses the divide and conquers algorithm, but unlikely, it does not divide the array into two equal parts to search the element. As compared to a linear search, binary search is more efficient, but the Interpolation search is more effective than any other searching algorithm .

    With Binary searching, if we want to locate the position of an element in the array, we require O(log n) time complexity, but we have another searching algorithm that is capable of searching an element with O(log log n) time complexity.

    As binary search always checks for the middle index, rather than considering the element, the interpolation search, consider the searched element and based on an algorithm check for those locations for which the value of the element being searched.

    Time Complexity

    Linear Search Binary Search Interpolation Search
    O(n) O(log n) O(log log n)

    Algorithm

    • The array must be sorted
    • Make a start =0 and end = n-1
    • Use a formula to locate the position, which brings us near to the searched element 
    pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))
    • If arr[pos] == target return the pos
    • If target > arr[pos] start = pos+1
    • Else end = pos-1

    Pseudocode 

    start =0
end = len(arr) -1
found = false
while found == false and start <=end
{            
   pos = start + (((end-start)/(arr[end]-arr[start])) * (target-arr[start]))       
   if arr[pos]==target
      {
         return pos
      }
   if target > arr[pos]
      {
          start = pos+1
      }
   else
      {
       end = pos-1
      }
}

    Implementation

    Python: 

    def Interpolation_Search (arr,target):
    start = 0
    end = len(arr)-1
    found = False

    while start <= end and found == False:
        if start == end:
            if arr[start] == target: 
                return "{} is at {} index".format(target,pos)
            return "not found"    

        pos = start + (((end-start)//(arr[end]-arr[start])) * (target-arr[start]))               

        if arr[pos] == target:      
            return "{} is at {} index".format(target,pos)  

        if arr[pos] < target:
            start = pos + 1;
        else:
            end = pos - 1;    

    return "Not Found"

arr = [10, 20, 40, 77, 86, 89, 91]
print(Interpolation_Search(arr, 86))

    Output: 

    86 is at 4 index

    People are also reading:

    Previous Tutorial Next Tutorial