interpolation-search/interpolationSearch.js

Implements interpolation search on sorted arrays, returning index or -1 if not found.

// Source: https://github.com/trekhleb/javascript-algorithms | License: MIT | Copyright 2018 Oleksii Trekhleb
// Provided via justclaw.it.com; keep this notice with the code.
/**
 * Interpolation search implementation.
 *
 * @param {*[]} sortedArray - sorted array with uniformly distributed values
 * @param {*} seekElement
 * @return {number}
 */
export default function interpolationSearch(sortedArray, seekElement) {
  let leftIndex = 0;
  let rightIndex = sortedArray.length - 1;

  while (leftIndex <= rightIndex) {
    const rangeDelta = sortedArray[rightIndex] - sortedArray[leftIndex];
    const indexDelta = rightIndex - leftIndex;
    const valueDelta = seekElement - sortedArray[leftIndex];

    // If valueDelta is less then zero it means that there is no seek element
    // exists in a

... (truncated -- full source via MCP)