在Node.js中实现插值查找算法也很简单。以下是一个用Node.js实现的插值查找算法的示例:
function interpolationSearch(arr, x) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
if (lo === hi) {
if (arr[lo] === x) return lo;
return -1;
}
let pos = lo + Math.floor(((x - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]));
if (arr[pos] === x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
// 示例用法
let arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47];
let x = 18; // 要查找的元素
let index = interpolationSearch(arr, x);
if (index !== -1)
console.log(`Element found at index ${index}`);
else
console.log("Element not found");
代码解释
插值查找函数(interpolationSearch):
- 初始化低端索引
lo
和高端索引hi
。 - 进入
while
循环,在lo
小于等于hi
且x
在数组范围内的情况下进行查找。 - 如果
lo
和hi
相等,直接判断arr[lo]
是否等于x
,是则返回索引,否则返回-1
。 - 计算估计位置
pos
。 - 如果
arr[pos]
等于x
,返回pos
。 - 如果
arr[pos]
小于x
,调整lo
为pos + 1
,否则调整hi
为pos - 1
。 - 如果查找失败,返回
-1
。
- 初始化低端索引
示例用法:
- 创建一个有序数组
arr
,并定义要查找的元素x
。 - 调用
interpolationSearch
函数查找元素x
在数组中的位置,并打印结果。
- 创建一个有序数组
这个实现与C#版本的逻辑相同,主要区别在于使用了JavaScript的语法。该算法在数据均匀分布的情况下性能会很好,最坏情况下的时间复杂度是O(n)。对于非均匀分布的数据,性能可能会退化,接近于线性查找。
4o