Interpolation Search algorithm

search
algorithm
interpolation-search

(Team) #1

Interpolation Search

Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values assigned to the keys (key values). It parallels how humans search through a telephone book for a particular name. In each search step, it calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible.

Implementation in various languages: here

You can contribute too!

Complexity Notation
Best case time complexity O(log log n)
Average case time complexity O(n)
Worst case time complexity O(n)
Space complexity O(1)

Procedure

Rest of the Interpolation algorithm is same except the above partition logic.

  • Step1: In a loop, calculate the value of “pos” using the probe position formula.
  • Step2: If it is a match, return the index of the item, and exit.
  • Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.
  • Step4: Repeat until a match is found or the sub-array reduces to zero.

Formula

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] --> Array where elements need to be searched
x     --> Element to be searched
lo    --> Starting index in arr[]
hi    --> Ending index in arr[]

Continue the discussion in the comments.