自学内容网 自学内容网

NodeJS实现插值查找算法

 在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");

代码解释

  1. 插值查找函数(interpolationSearch):

    • 初始化低端索引lo和高端索引hi
    • 进入while循环,在lo小于等于hix在数组范围内的情况下进行查找。
    • 如果lohi相等,直接判断arr[lo]是否等于x,是则返回索引,否则返回-1
    • 计算估计位置pos
    • 如果arr[pos]等于x,返回pos
    • 如果arr[pos]小于x,调整lopos + 1,否则调整hipos - 1
    • 如果查找失败,返回-1
  2. 示例用法:

    • 创建一个有序数组arr,并定义要查找的元素x
    • 调用interpolationSearch函数查找元素x在数组中的位置,并打印结果。

这个实现与C#版本的逻辑相同,主要区别在于使用了JavaScript的语法。该算法在数据均匀分布的情况下性能会很好,最坏情况下的时间复杂度是O(n)。对于非均匀分布的数据,性能可能会退化,接近于线性查找。

4o


原文地址:https://blog.csdn.net/zdh13370188237/article/details/140540488

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!