How to search map in between value efficiently?

Question

Map<Long, Object> map = new TreeMap<>();
map.put(100, object100);
map.put(120, object120);
map.put(200, object200);
map.put(277, object277);
map.put(300, object300);
map.put(348, object348);
map.put(400, object400);
//...

If a method gets a value in between the map's key and the next map's key, it would return the first key's object. For example, if the search method is invoked with the value 350, it should return object348.

The difference of value in the keys is not fixed.

But searching like that requires the iteration through all the entries until it gets the correct value. So, how do I make this efficient?

Answer 1

I'm not absolutely clear on whether you want only the object for the key which is lower than the target number, or the object for the nearest key either below or above.

I suspect you're asking just for the object for the key below, in which case NavigableMap.floorKey(K) should find what you seek.

But just in case you'd prefer to find the object whose key has the value nearest to the target value, then this should do what you need:

public static Object findNearestTo(long targetNumber) {
    if (map.isEmpty()) {
        return null;  // or throw an appropriate exception.
    }
    Object exactMatch = map.get(targetNumber);
    if (exactMatch != null) {
        return exactMatch;
    }
    Long nearestBelow = map.floorKey(targetNumber);
    Long nearestAbove = map.ceilingKey(targetNumber);
    if (nearestBelow == null) {
        return map.get(nearestAbove);
    } else if (nearestAbove == null) {
        return map.get(nearestBelow);
    }
    if (targetNumber - nearestBelow <= nearestAbove - targetNumber) {
        return map.get(nearestBelow);
    } else {
        return map.get(nearestAbove);
    }
}

Note that where the target number is an equal distance from the nearest below and the nearest above, it will favour the object in the key with the lower value. But you can favour the higher value simply by changing <= to < in the final if test.