java - Java 中的范围查找

Question

假设，我有一个未排序的重叠范围数组。每个 range 只是一对整数 begin 和 end。现在我想查找给定的 key 是否至少属于 ranges 之一。可能，我还必须知道它所属的范围。

我们可以假设 ranges 数组占用 ~1M 并适合内存。我正在寻找一种简单的算法，它仅使用标准 JDK 集合，不使用任何 3d 方库和特殊数据结构，但运行速度相当快。

你有什么建议？

Answer 1

按自定义 Comparator 对范围进行数字排序, 然后为每个键 k 构建一个单元素范围 [k, k] 并执行 binary search对于此范围，使用不同的 Comparator .

Comparator用于搜索的 compare(x,y)应该返回

• <0如果x.max < y.min
• >0如果x.min > y.max
• 0否则(它的两个范围参数重叠)。

如@Per 所述，您需要一个不同的、更严格的 Comparator用于排序，但前两个子句仍然成立。

即使范围重叠，这也应该有效，尽管您可能希望在排序后合并重叠范围以加快搜索速度。合并可以在 O(N) 时间内完成。

这实际上是一个静态的 interval tree ，即没有 O(lg N) 插入或删除，就像排序数组可以被视为静态二叉搜索树一样。