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