JavaScript Interpolation Search<!-- --> | <!-- -->Patrick Desjardins Blog
Patrick Desjardins Blog

# JavaScript Interpolation Search

Posted on: June 22, 2017

If an array contains element that are uniformly distributed, it's possible to each an asymptotic analysis of Big `O(log log n)`.

The whole problem is about determining the position. This is done by finding the position. This is the iterative solution.

```1var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];2
3console.log("Found at position :" + interpolationSearch(arrayToSearch, 2));4console.log("Found at position :" + interpolationSearch(arrayToSearch, 12));5console.log("Found at position :" + interpolationSearch(arrayToSearch, 35));6console.log("Found at position :" + interpolationSearch(arrayToSearch, 44444));7
8function interpolationSearch(arrayToSearch, valueToSearch) {9  var length = arrayToSearch.length;10  var low = 0;11  var high = length - 1;12  var position = -1;13  var delta = -1;14  while (15    low <= high &&16    valueToSearch >= arrayToSearch[low] &&17    valueToSearch <= arrayToSearch[high]18  ) {19    delta =20      (valueToSearch - arrayToSearch[low]) /21      (arrayToSearch[high] - arrayToSearch[low]);22    position = low + Math.floor((high - low) * delta);23    if (arrayToSearch[position] == valueToSearch) {24      return position;25    }26    if (arrayToSearch[position] < valueToSearch) {27      low = position + 1;28    } else {29      high = position - 1;30    }31  }32
33  return -1;34}```

This can be easily transformed into the a recursive algorithm.

```1var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];2var length = arrayToSearch.length;3var low = 0;4var high = length - 1;5console.log(6  "Found at position :" + interpolationSearch(arrayToSearch, 2, 0, high)7);8console.log(9  "Found at position :" + interpolationSearch(arrayToSearch, 12, 0, high)10);11console.log(12  "Found at position :" + interpolationSearch(arrayToSearch, 35, 0, high)13);14console.log(15  "Found at position :" + interpolationSearch(arrayToSearch, 44444, 0, high)16);17
18function interpolationSearch(arrayToSearch, valueToSearch, low, high) {19  if (20    low <= high &&21    valueToSearch >= arrayToSearch[low] &&22    valueToSearch <= arrayToSearch[high]23  ) {24    var delta =25      (valueToSearch - arrayToSearch[low]) /26      (arrayToSearch[high] - arrayToSearch[low]);27    var position = low + Math.floor((high - low) * delta);28    if (arrayToSearch[position] == valueToSearch) {29      return position;30    }31    if (arrayToSearch[position] < valueToSearch) {32      low = position + 1;33    } else {34      high = position - 1;35    }36    return interpolationSearch(arrayToSearch, valueToSearch, low, high);37  }38
39  return -1;40}```