Return key when value in range

Question

I have a large data set where values are non-overlapping ranges that are sorted in increasing order. There are holes between ranges and keys (type is long) can be assigned to multiple ranges:

[100,300] K1
[310,400] K1
[401,600] K2
[650,1000] K3
...

I need to find a key for a given value. If value doesn't belong to any range, I should return 0.

My approach was to build

NavigableMap<Long, Range> map = new TreeMap<>();

and then

map.put(K1, new Range(100,300);
...

That results in a quite large map that is sorted by keys. This is not what I want since I would prefer to have a map that is sorted by range values so that I can easily conduct binary search. My problem is that I don't know how to use this map to find key for a given value. For example, value 101 should return K1, 500 should return K2, 301 should return 0. Is there any way to achieve what I want using NavigableMap or am I using the wrong approach?

Answer 1

Since you have stated the ranges cannot overlap but may have gaps, you should use a NavigableMap<Range,Long> with a Range representation that uses only the lower bound of the range for the hashCode and equals implementations.

Note that I have reversed the order of the generic types in the NavigableMap from what you show in your code sample.

To search for a value you want the largest entry (i.e. the entry with the largest lower bound) that is less than the search key.

Conversely, if you used the upper bound in the Range object, you'd want the smallest entry larger than the search key.

After you find the appropriate Map entry you have to double check that the key value is actually within range, due to the possible gaps.