如何从给定数字的连续范围集中查找范围

Question

简而言之，这就是我想做的：

我有一个收藏 Range 连续的对象（不重叠，它们之间没有间隙），每个对象都包含一个 start 和 end int，以及对另一个对象的引用 obj. 。这些范围没有固定的大小（第一个可以是 1-49，第二个可以是 50-221，等等）。这个集合可能会变得相当大。

我希望找到一种方法来查找包含给定数字的范围（或更具体地说，它引用的对象），而不必迭代整个集合检查每个范围以查看它是否包含该数字。这些查找将频繁执行，因此速度/性能是关键。

有谁知道可以帮助我的算法/方程？我正在用 Java 编写。如果需要，我可以提供更多详细信息，但我想我会尽量保持简单。

谢谢。

Answer 1

如果听起来你想使用 TreeMap, ，其中键是范围的底部，值是 Range 目的。

然后要确定正确的范围，只需使用 floorEntry() 快速获得最接近（小于或等于）的方法 Range, ，其中应该包含密钥，如下所示：

    TreeMap<Integer, Range> map = new TreeMap<>();
    map.put(1, new Range(1, 10));
    map.put(11, new Range(11, 30));
    map.put(31, new Range(31, 100));

    // int key = 0; // null
    // int key = 1; // Range [start=1, end=10]
    // int key = 11; // Range [start=11, end=30]
    // int key = 21; // Range [start=11, end=30]
    // int key = 31; // Range [start=31, end=100]
    // int key = 41; // Range [start=31, end=100]
    int key = 101; // Range [start=31, end=100]
    // etc.

    Range r = null;
    Map.Entry<Integer, Range> m = map.floorEntry(key);
    if (m != null) {
        r = m.getValue();
    }
    System.out.println(r);

由于树始终按底部范围边界的自然顺序排序，因此所有搜索在最坏的情况下将是 O(log(n))。

您需要添加一些健全性检查，以检查您的密钥何时完全超出范围（例如，当它们的密钥超出地图末尾时，它会返回最后一个 Range 在地图中），但这应该能让您了解如何继续。

Answer 2

假设您的查找至关重要，并且您可以节省 O(N) 内存和大约 O(N^2) 预处理时间，则算法将是：

• 介绍一个类 ObjectsInRange, ， 其中包含：范围开始（int startOfRange）和一组对象（Set<Object> objects)
• 介绍一个 ArrayList<ObjectsInRange> oir, ，其中将包含 ObjectsInRange 排序依据 startOfRange
• 对于每个 Range r,确保存在 ObjectsInRange （我们称他们为 a 和 b）这样 a.startOfRange = r.start 和 b.startOfRange = b.end. 。那么，对于所有 ObjectsInRange x 之间 a, ，直到（但不包括） b, ， 添加 r.obj 给他们的 x.objects 放

那么，查找如下：

• 对于整数 x, ，找到这样的 i 那 oir[i].startOfRange <= x 和 oir[i+1].startOfRange > x
• 笔记： i 可以在 O(log N) 时间内找到二分法！
• 你的对象是 oir[i].objects

Answer 3

如果集合是有序的，那么您可以实现二分搜索以在 O(log(n)) 时间内找到正确的范围。对于非常大的集合，它的效率不如散列，但如果范围少于 1000 个左右，它可能会更快（因为它更简单）。