Using java map for range searches

I can think of a number of possible solutions for the more general problem where the ranges are not uniform and there are 'holes'. The simplest are:

1. Simply populate a Map for all valid key values, with multiple keys mapping to the same value. Assuming that you use HashMaps, this should be the most time efficient (O(1) lookups), though you have more work at setup time and you use more space.
2. Use a NavigableMap and use floorEntry(key) to do the lookups. This should be less time efficient (O(log(N) lookups) but more space efficient.

Here's a solution using NavigableMaps that allows for 'holes' in the mapping.

private static class Range {
   public int upper, value;
   ...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0));       // 0..3     => 0
map.put(5, new Range(10, 1));      // 5..10    => 1
map.put(100, new Range(200, 2));   // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
    // too small
} else if (key <= entry.getValue().upper) {
    return entry.getValue().value;
} else {
    // too large or in a hole
}

On the other hand, if there are no 'holes' the solution is simpler:

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0);    // 0..4     => 0
map.put(5, 1);    // 5..10    => 1
map.put(11, 2);   // 11..200  => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
    // out of range
} else {
   return map.floorEntry(key).getValue();
}

Pseudo-code:

1. Store the range bounds in a flat array: new int[] {0, 3, 5, 15, 100, 300}.
2. Binary search through the array as if inserting a number into the array. See Arrays.binarySearch().
3. If the insertion point is even, the number does not fit into any range.
4. If the insertion point is odd, it fits into the corresponding range. For example, the insertion point for 10 in the above array would be 3, placing it between 5 and 15, so it belongs in the second range.