java - Java：从集合中获取范围内的值

Question

假设我有一个（排序的）集合，可以是 List、Map、Set 或其他任何东西。获得一定范围内的所有值的最佳解决方案是什么。

例如，我有一个整数列表，如下所示： [1, 5, 7, 9, 12, 30, 50, 100]

我想检索 8 +- 5 个值，这将是： [5, 7, 9, 12]

我知道 NavigableMap 非常有趣，但是我只能使用它检索一个元素。

对于比 O(N)、O(NLogN) 或我可以使用的特定集合更复杂的算法，你有什么建议吗？

非常感谢！科斯蒂

Answer 1

最接近您正在寻找的是 a NavigableSet，它具有以下方法：

NavigableSet<E> subSet(E fromElement,
                   boolean fromInclusive,
                   E toElement,
                   boolean toInclusive)

如果你有一个排序列表，那么使用Collections.binarySearch()两次可以让你快速找到范围内第一个和最后一个元素的索引。

另外，请注意，如果您需要的是 Map，NavigableMap则具有类似的方法。

Answer 2

如果你有一个排序数组，你可以二进制搜索范围的最小值，然后在 O(log(n)) 中二进制搜索范围的最大值。