How to search within list of integer ranges efficiently - java

user_15999300 0
Viewed 342

How to search within list of integer ranges efficiently?

I have list of ranges with some duplicate values. I want to get value, if input number is within range.

e.g.

Range Start Range End Value
10 75 A
95 200 A
300 455 B
570 650 C
201 250 A
255 275 B

Note: Start and end ranges are not overlapped.

  • Input 260 Expected output B
  • Input 195 Expected output A

Currently, I am saving in HashMap <String, String> and Storing {“10-75” , A} {’95-200”, B}… I am

  • looping through all keys of Map,
  • split each key,
  • convert to int and
  • check given number is within range or not.
  • if yes get value for that key

I am thinking there may be some more efficient way to handle this in Java.

Any help would be greatly appreciated.

range hashmap list java
3 Answers

You could do it using a TreeMap and Entry like this using regular Java. If no range exists for the supplied argument it returns Not Found

Here is the map for containing the ranges.

  • it is a TreeMap
  • the key is the lower part of a range.
  • the value is a AbstractMap.SimpleEntry with the upper part of the range and the String.
NavigableMap<Integer, AbstractMap.SimpleEntry<Integer,String>> nmap =
        new TreeMap<>();

The method for constructing the map.

public static void build(
        NavigableMap<Integer, AbstractMap.SimpleEntry<Integer, String>> map,
                                         int start, int end, String v) {
        AbstractMap.SimpleEntry<Integer, String> e = new 
                    AbstractMap.SimpleEntry<Integer,String>(end,v);
        map.put(start, e);
}

A lambda for retrieving the String.

Function<Integer,String> get = k->{
        Entry<Integer, AbstractMap.SimpleEntry<Integer,String>> entry = 
                             nmap.floorEntry(k);
        if (entry == null) {
                  return "Not Found";
        }
        if (k > entry.getValue().getKey()) {
                  return "Not Found";
        }
        return entry.getValue().getValue();        
};

Building the map for each range

build(nmap, 10, 75, "A");
build(nmap, 95, 200, "A");
build(nmap, 300, 455, "B");
build(nmap, 570, 650, "C");
build(nmap, 201, 250, "A");
build(nmap, 255, 275, "B");

Testing

int[] testData = { 9, 23, 255, 99, 94, 201 };
for (int i : testData) {
    System.out.printf("%4d -> %s%n",i, get.apply(i));
}

Prints

   9 -> Not Found
  23 -> A
 255 -> B
  99 -> A
  94 -> Not Found
 201 -> A
user_15525340

You can use Guava's RangeMap:

RangeMap<Integer, Character> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(10, 75), 'A');
rangeMap.put(Range.closed(95, 200), 'A');
rangeMap.put(Range.closed(300, 455), 'B');
rangeMap.put(Range.closed(570, 650), 'C');
rangeMap.put(Range.closed(201, 250), 'A');
rangeMap.put(Range.closed(255, 275), 'B');

Character character = rangeMap.get(61);
Character character2 = rangeMap.get(244);
Character character3 = rangeMap.get(270);

System.out.println(character);
System.out.println(character2);
System.out.println(character3);

Output:

A
A
B

Note: for some reason, it's marked with @Beta https://github.com/google/guava/issues/3376 so I would want to make sure it's OK if it's for production use.

user_133128200

Why don't you try three if-else statements?

Assumptions: Start and End values of ranges are considered as values within the given range.

'D' denotes that the given value belongs to neither of the defined range values.

Sample code:

 public static char findRangeValue(int number){

        if((number >= 10 && number <=75) ||(number >= 95 && number <=250) ){
            return 'A';
        }else if((number >= 255 && number <=275) ||(number >= 300 && number <=455)  ){
            return 'B';
        }else if(number >= 570 && number <=650 ){
            return 'C';
        }
           return 'D';
    }

Sample method call and outputs :

  public static void main(String[] args) {

        System.out.println(findRangeValue(265));
        System.out.println(findRangeValue(11));
        System.out.println(findRangeValue(575));
    }

Outputs:

B
A
C
user_125479540
Related