java - 如何从给定数字的一组连续范围中查找范围

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))。

当您的键完全超出范围时(例如，当它们的键超出 map 的末尾时，它会返回最后一个 Range map )，但这应该能让您了解如何继续。