需要找到一個數字是否已經存在於任何給定的範圍內

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字節數，同時做一個表中的線性搜索，其中就結束地址被存儲，性能非常低，因爲表可以有大約50,000到100,000個條目。

謝謝

Answer 1

你可以用間隔樹來做到這一點。 對於每個範圍，在間隔樹中插入一個條目。

現在，如果您想要搜索數字'k'所在的範圍。 在區間樹中搜索。 同樣，每當範圍更改時，從Interval中刪除該範圍，然後將其重新插入新值。