Java: Get values in a range from a collection

collections, java

Solution

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.

Problem

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

Original source