Data Structure & Algorithm: Interpolation Search

By | January 12, 2020
Interpolation Search

Interpolation search is a searching algorithm that applies on 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.

Vamware

As binary search always checks for the middle index, rather than considering the element, but the interpolation search, consider the searched element and based on an algorithm check for those locations for which the value of 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

Leave a Reply

Your email address will not be published. Required fields are marked *