added interpolation search

[webcoderspeed]

Issue

• https://github.com/akshitagit/JavaScript/issues/115

  Explanation of the algorithm

  • The interpolation search algorithm is an improvement over the binary search algorithm.
  • The interpolation search algorithm works on the probing position of the required value.
  • For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.
  • The idea of formula is to return higher value of pos when element to be searched is closer to arr[hi]. And smaller value when closer to arr[lo]

  Pseudocode

  • 1. Find the position to be searched
  • 2. If it is a match, return the index of the item, and exit.
  • 3. 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.
  • 4. Repeat until a match is found or the sub-array reduces to zero.

  Example

  • interpolationSearch([1, 2, 3, 4, 5], 3) // returns 2
  • interpolationSearch([1, 2, 3, 4, 5], 6) // returns -1
  • interpolationSearch([1, 2, 3, 4, 5], 1) // returns 0

  Time Complexity

  • Best Case: O(1)
  • Average Case: O(log(log(n)))
  • Worst Case: O(n)

  Space Complexity

  • O(1)