JavaScript中的插值搜索

插值搜索

插值搜索是一种算法，用于在已按分配给键的数字值（键值）排序的数组中搜索键。

例如

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

它执行以下操作以找到位置-

//公式的想法是返回更高的pos值

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

//靠近arr [lo]时较小的值

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

键-

• arr []-需要搜索元素的数组

• x-要搜索的元素

• lo-arr中的起始索引[]

• 嗨-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));

输出结果

以下是控制台上的输出-

10