JavaScript 中的插值搜索

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 14:04:17

插值搜索

插值搜索是一种在按分配给键的数值(键值)排序的数组中搜索键的算法。

例如

假设我们有一个由 n 个均匀分布的值 arr[] 组成的排序数组，我们需要编写一个函数来搜索数组中的特定元素目标。

它执行以下操作来找到位置 −

// 该公式的思想是当要搜索的元素更接近 arr[hi] 时返回更高的 pos 值

// 当要搜索的元素更接近 arr[hi] 时。并且

// 越接近 arr[lo]，值越小

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))

键 −

arr[] - 需要搜索元素的数组
x - 要搜索的元素
lo - arr[] 中的起始索引
hi - arr[] 中的结束索引

我们需要编写一个 JavaScript 函数，该函数将数字数组作为第一个参数，将搜索目标作为第二个参数。

该函数应使用插值搜索算法在数组。

示例

以下是代码 −

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const interpolationSearch = (arr = [], target) => {
   let left = 0;
   let right = arr.length - 1;
   while (left <= right) {
      const rangeDelta = arr[right] - arr[left];
      const indexDelta = right - left;
      const valueDelta = target - arr[left];
      if (valueDelta < 0) {
         return -1;
      }
      if (!rangeDelta) {
         return arr[left] === target ? left : -1;
      }
      const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
      if (arr[middleIndex] === target) {
         return middleIndex;
      }
      if (arr[middleIndex] < target) {
         left = middleIndex + 1;
      } else {
         right = middleIndex - 1;
      }
   };
   return -1;
};
console.log(interpolationSearch(arr, target));