讨论/算法和数据结构/查询IP所在区间/
查询IP所在区间

IP检索问题

描述:

我们有一系列如下格式的IP段及其对应的名称,

[(IP_start, IP_end, name), (IP_start, IP_end, name), ...]

[IP_start, IP_end]区间可能互相有重叠!!

现拿到K个待查询 IP,请返回它们各自所属的网段名称,即 name。每个 ip 可能属于多个区间!

注意:

1.IP 段可做预处理。假设K很大,重点在于优化每个 query 的耗时。

求问如何不用 O(K*N)的暴力方法解决该问题呢?是否有 O(K logN) 的查询方法?

ip段肯定不重叠的,只需要把ip段排序,然后对于每个ip,二分即可