Java: Get values in a range from a collection

Question

Suppose I have a (sorted) collection, be that a List, a Map, a Set or anything else. What would be the best solution to get all the values within a certain range.

For instance I have a list of Integers like so: [1, 5, 7, 9, 12, 30, 50, 100]

I would like to retrieve the 8 +- 5 values, which is going to be: [5, 7, 9, 12]

I know about the NavigableMap which is quite interesting, however I can only retrieve one element using it.

Do you have any tips on an algorithm that has a better complexity than O(N), maybe O(NLogN) or a specific collection I could use?

Thanks very much! Costi

Answer 1

The closest to what you're looking for is a NavigableSet, which has the following method:

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

If you have a sorted list, then using Collections.binarySearch() twice would allow you to quickly find the index of the first and last elements in the range.

Also, note that if what you need is a Map, NavigableMap has a similar method.