Home » Web » Javascript » JavaScript Interpolation Search

JavaScript Interpolation Search

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;
}

If you like my article, think to buy my annual book, professionally edited by a proofreader. directly from me or on Amazon.

Leave a Reply

Your email address will not be published. Required fields are marked *