JavaScript Interpolation Search

Posted on: 2017-06-22

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.

var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];

console.log("Found at position :" + interpolationSearch(arrayToSearch, 2));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 12));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 35));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 44444));

function interpolationSearch(arrayToSearch, valueToSearch) {
  var length = arrayToSearch.length;
  var low = 0;
  var high = length - 1;
  var position = -1;
  var delta = -1;
  while (
    low <= high &&
    valueToSearch >= arrayToSearch[low] &&
    valueToSearch <= arrayToSearch[high]
  ) {
    delta =
      (valueToSearch - arrayToSearch[low]) /
      (arrayToSearch[high] - arrayToSearch[low]);
    position = low + Math.floor((high - low) * delta);
    if (arrayToSearch[position] == valueToSearch) {
      return position;
    }
    if (arrayToSearch[position] < valueToSearch) {
      low = position + 1;
    } else {
      high = position - 1;
    }
  }

  return -1;
}

This can be easily transformed into the a recursive algorithm.

var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];
var length = arrayToSearch.length;
var low = 0;
var high = length - 1;
console.log(
  "Found at position :" + interpolationSearch(arrayToSearch, 2, 0, high)
);
console.log(
  "Found at position :" + interpolationSearch(arrayToSearch, 12, 0, high)
);
console.log(
  "Found at position :" + interpolationSearch(arrayToSearch, 35, 0, high)
);
console.log(
  "Found at position :" + interpolationSearch(arrayToSearch, 44444, 0, high)
);

function interpolationSearch(arrayToSearch, valueToSearch, low, high) {
  if (
    low <= high &&
    valueToSearch >= arrayToSearch[low] &&
    valueToSearch <= arrayToSearch[high]
  ) {
    var delta =
      (valueToSearch - arrayToSearch[low]) /
      (arrayToSearch[high] - arrayToSearch[low]);
    var position = low + Math.floor((high - low) * delta);
    if (arrayToSearch[position] == valueToSearch) {
      return position;
    }
    if (arrayToSearch[position] < valueToSearch) {
      low = position + 1;
    } else {
      high = position - 1;
    }
    return interpolationSearch(arrayToSearch, valueToSearch, low, high);
  }

  return -1;
}