How to find if a number is contained in an array of number ranges in java

Question

I have an array of java objects.

• Each object stores two longs that define a number range.
• I already have a guarantee that for all the objects in the range, the number ranges don't overlap.

I want a quick of finding a particular object in the array, given a number which may (or may not) fall within one of the number ranges defined by the objects.

I was hoping to do this using Array.binarySearch but that doesn't look appropriate.

Any thoughts on the best way to do this?

Answer 1

Have the items in the array implement the Comparable interface, by letting item a be bigger than the other item b if a.start > b.end. Then sort the array using this comparison.

Then to find if a number x is in a range in a item in the array, do a search in the array for the first item k with k.end >= x, and check if k.start <= x. If so, k is the range. Else, x is not in any range in the array.

Answer 2

Use a TreeMap. The key is the lower of the two Long range bounds; the value is the object.

private TreeMap<Long, T> map = new TreeMap<Long, T>();

void insertObject(T object) {
    map.put(object, object.getLowerRangeBoundary());
}

T getObjectByKeyInRange(Long query) {
    // Get the first Object in the tree that corresponds with the query
    Map.Entry<Long, T> e = map.floorEntry(query);

    // If there's no entry, then the query value is lower than all ranges in the tree
    if (e == null) {
        return null;
    }

    T target = e.getValue();
    // "target" is the only object that can contain the query value
    // If the query value is within the range of "target", then it is our object
    if (query < target.getUpperRangeBoundary()) {
        return target;
    }

    // Nobody has the query value in their range; return null
    return null;
}

Answer 3

You can actually handle this very efficiently (for large numbers of ranges and millions of queries on the ranges) and allow for the ranges to overlap.

Pseudo code:

Let rangeMap be a TreeMap:

foreach(Range r in ranges)
    rangeMap[r.start].Increment();
    rangeMap[r.end].Decrement();

rangeMap.GreatestLowerBound(i) will now return the number of ranges that a given integer i belongs to ( i.e. GreatestLowerBound is the largest number <= i).

You can do better still in terms of practical performance if you know the number of ranges up front... by allocating a single array, populating it with "deltaRange", then "integrate" to get an array showing the cumulative "ranges" for each number x.