我需要找出一个数字是否已经存在于任何给定的范围内

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字节的数字，它是从运行时接收的缓冲区中派生出来的，当在存储开始和结束addr的表中进行线性搜索时，性能非常低，因为表可以有大约50,000到100,000个条目。

谢谢

Answer 1

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

现在如果你想搜索数字'k‘所在的范围。在区间树中搜索。此外，只要某个范围发生更改，就从Interval中删除该范围，然后用新值重新插入。