Interpolation Search

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).

For example we have a sorted array of n uniformly distributed values arr[], and we need to write a function to search for a particular element x in the array.

Linear Search finds the element in O(n) time, Jump Search takes O(√ n) time and Binary Search take O(Log n) time.

The Interpolation Search is an improvement over 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. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

To find the position to be searched, it uses following formula:

  1. // The idea of formula is to return higher value of pos
  2. // when element to be searched is closer to arr[hi]. And
  3. // smaller value when closer to arr[lo]
  4. pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
  6. arr[] - Array where elements need to be searched
  7. x - Element to be searched
  8. lo - Starting index in arr[]
  9. hi - Ending index in arr[]

Complexity

Time complexity: O(log(log(n))

References