Using java map for range searches

Question

I have a use case where if a number lies between 0-10 it should return 0 and if it lies between 11-20 it should return 1 etc

0 => 0-3, (0 and 3 are inclusive) 1 => 4-15, (4 and 15 are inclusive) 2 => 16-40, (16 and 40 are inclusive) 3 => 41-88, (41 and 88 are inclusive) 5 => 89-300 (89 and 300 are inclusive) 

I was thinking how could I implement and was thinking java maps, but it does not allow range searching

I am interested in something like this , I have a function

int foo() {  } 

if foo returns 5 , since it lies between 0 to 10 I would use 0, if foo return 25 it would use 2.

Any ideas

Edit : Actually the ranges are not as simple as 0-10, 11-20. I want to be able to do range searches. Sorry about the confusion. Based on the queries I have added the correct example, the numbers are continous

Answer 1

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(); } 

Answer 2

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.