algorithm - 对范围列表执行查找

Question

我有一个要查询的范围列表。范围是有序的，不重叠。

前任：

1-10、11-17、18-20、21-30等...

目前我使用修改后的二进制搜索。但是我现在有一个新列表……除了不重叠的范围之外，新列表现在可以被位掩码。

前任：

0-255、256-287、288-303等...

有几千个范围，以大约 500,000 结尾

我将在 c 中实现它，但语言并不重要。我只是在寻找一些关于如何利用这个新属性的想法。有没有人遇到过这个/读过它？如果有人有任何想法，他们将是最受欢迎的。:)

Answer 1

保存一个大小为 500000 的位向量怎么样？这将需要大约 61kb。

然后您可以通过执行 AND 来查询一个数字是否在 O(1) 的范围内。您还可以同时查询多个值。此外，设置范围位向量将非常快，因为您不需要排序。