Javascript: интерполяционный поиск

Функция интерполяционного поиска, принимает массив и значение для поиска.

Алгоритм начинается с установки нижнего и верхнего указателей на начало и конец массива. Затем он вычисляет среднюю точку, используя формулу интерполяции:

mid = low + ((x - arr[low]) * (high - low)) / (arr[high] - arr[low])

После чего, скрипт сравнивает средний элемент массива со значением. Если он больше, он уменьшает верхний указатель, если он меньше, увеличивает нижний указатель и проверяет снова.

Пока не обнаружит, что значение или нижний указатель больше, чем верхний указатель.

Если значение найдено, возвращается его индекс, если нет, возвращается -1.

Функция интерполяционного поиска

function interpolationSearch(arr, x) {
  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (arr[low] <= x && arr[high] >= x) {
    mid = low + ((x - arr[low]) * (high - low)) / (arr[high] - arr[low]);

    if (arr[mid] < x) {
      low = mid + 1;
    } else if (arr[mid] > x) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  if (arr[low] === x) {
    return low;
  } else {
    return -1;
  }
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(interpolationSearch(arr, 6)); // 5