在 Java 中使用什么数据类型来匹配区间？

Question

我有一个实现非重叠范围的对象列表，例如：

1 to 10
11 to 20
21 to 50
51 to 100

它们提供min()并max()检索这些值。

我需要一个数据存储来轻松检索正确的对象，给定一个必须在其间隔内的值。

我能想到的最简单的方法是创建一个有序的数组列表并简单地遍历它，直到找到正确的间隔。所以在这种情况下，查找是在 O(N) 中完成的。

标准 Java 库中是否有更有效的数据结构来完成此任务？

Answer 1

您可以尝试使用该NavigableMap方法，此答案中对此方法进行了解释：Using java map for range search , the 'noholes' aapproach。

使用 TreeMap 的示例实现：

// Create TreeMap
NavigableMap<Integer, MyInterval> map = new TreeMap<>();

// Putting values
map.put(interval1.min(), myInterval);
map.put(interval2.min(), myInterval);

// Retrieving values
int value = 15;
MyInterval interval = map.floorEntry(value).getValue();

// Check if value is smaller than max()
if (value <= interval.max())
    return interval;
return null;