Interpolation Search

jsbin.citeson.js

/*
 * Performance Test at
 * https://jsperf.com/interpolate-search/1
 */

"use strict";

function interpolateSearch(array, target) {
  var high = array.length - 1;
  var low = 0; // lowest possible index of an array is 0
  var maxValue = array[array.length - 1];
  var minValue = array[0];
  var range = maxValue - minValue;
  /* Point-Slope Formula:
   *
   * y = m(x - x1) + y1
   * refactored to be
   * y = ((y2 - y1) / (x2 - x1)) * (x - x1) + y1
   *
   */
  var index = high / range * (target - minValue) + low;
  if (index) {
    return index;
  } else {
    return false;
  }
}