c - 需要查找一个数字是否已经存在于任何给定范围内

Question

我配置了多个可以动态增加/减少的范围，我需要找到最快的方法来查找给定数字是否存在是任何范围，如果是则返回范围？有人可以建议我用 C 中最快的算法或数据结构来做这样的操作吗？

代码片段如下：

addr = GET_U32BIT(buf);

    /* Search for the corresponding address */
    while(i < addr_table_size)
    {
        if((addr >= ntohl(table->addr_id[i].start_addr)) && \
                (addr <= ntohl(table->addr_id[i].end_addr)))
        {
            addr_present = 1;
            range_id = i;
            break;          
        }
        i++;
    }

在上面的代码中，addr 是一个 4 字节的数字，它是从运行时接收的缓冲区中派生的，在存储 start 和 end addr 的表中进行线性搜索时，性能非常低，因为 table 可以有大约 50,000 到 100,000条目。

谢谢

Answer 1

您可以使用区间树来做到这一点。对于每个范围，在区间树中插入一个条目。

现在，如果您想搜索数字“k”所在的范围。在区间树中搜索。此外，每当范围更改时，从 Interval 中删除该范围，然后重新插入新值。