Nodejs 求js最高效算法：范围查找

Node.js 中高效的范围查找算法

需求描述

假设有一条长街，门牌号从0到1000，每个区间售卖不同的商品：

• 0-100：卖鱼
• 101-203：卖菜
• 204-500：卖肉
• 501-1000：卖鸡蛋

我们需要根据给定的门牌号（例如：75），找出该门牌号对应的售卖商品。

解决方案

为了实现高效的范围查找，我们可以使用二分查找算法。二分查找适用于有序数组，能够在对数时间内找到目标值的位置。在这个场景中，我们首先需要将区间转换为一个有序数组。

const intervals = [
    { start: 0, end: 100, product: '鱼' },
    { start: 101, end: 203, product: '菜' },
    { start: 204, end: 500, product: '肉' },
    { start: 501, end: 1000, product: '鸡蛋' }
];

function findProductByHouseNumber(houseNumber) {
    let left = 0;
    let right = intervals.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (intervals[mid].start <= houseNumber && houseNumber <= intervals[mid].end) {
            return intervals[mid].product;
        }

        if (houseNumber < intervals[mid].start) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return '未找到';
}

// 示例调用
console.log(findProductByHouseNumber(75)); // 输出: 鱼

解释

1. 数据结构：我们将每个区间的起始和结束位置以及对应的售卖商品存储在一个对象数组中。
2. 二分查找：我们定义了 findProductByHouseNumber 函数来实现二分查找。函数接收一个门牌号作为参数。
3. 查找过程：
   • 初始化 left 和 right 指针分别指向数组的首尾。
   • 在 left 小于等于 right 的情况下进行循环。
   • 计算中间索引 mid。
   • 如果门牌号位于当前区间的范围内，则返回对应的售卖商品。
   • 如果门牌号小于当前区间的起始位置，则调整 right 指针。
   • 否则，调整 left 指针。
4. 返回结果：如果在所有区间中都没有找到匹配项，则返回 “未找到”。

这种方法的时间复杂度为 O(log n)，非常适合大规模数据的查找。

嗯，而且长度还不太均匀，有的很大，有的很小。。。 …

如果是数据库，建个索引就可以了

40亿数据量的原始表不适合用于查询待查门牌号是卖什么的。 因为号段连续，就可以另建门牌号段表，50w记录那个。就是 xujun52011说的var types = [{begin:x,end:y,type:z},…] 你不是放在数据库里面吗？那如果要查门牌号为xxx的是卖什么，就对types的begin建立索引， 然后选择begin小于等于xxx的号段记录中最大的那条。 select top 1 type from types where begin<=xxx order by begin desc 50万记录加单键有序索引，速度应该没问题吧