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}