/**
 * Interpolation Search
 *
 * Time Complexity:
 * -Best case: O(1)
 * -Worst case: O(n)
 * -O((log(log(n))) If the data are uniformly distributed
 *
 *
 */

export function interpolationSearch(arr, key) {
  const length = arr.length - 1
  let low = 0
  let high = length
  let position = -1
  let delta = -1

  // Because the array is sorted the key must be between low and high
  while (low = arr[low] && key