Usando el mapa de Java para búsquedas de rango

Tengo un caso de uso donde si un número se encuentra entre 0-10 debería devolver 0 y si se encuentra entre 11-20 debería devolver 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) 

Estaba pensando cómo podría implementar y estaba pensando en mapas de Java, pero no permite la búsqueda de rango

Estoy interesado en algo como esto, tengo una función

 int foo() { } 

si foo devuelve 5, dado que está entre 0 y 10, usaría 0, si devuelve 25, usaría 2.

Algunas ideas

Editar: En realidad, los rangos no son tan simples como 0-10, 11-20. Quiero poder hacer búsquedas de rango. Perdón por la confusión. En base a las consultas que he agregado el ejemplo correcto, los números son continuos

Puedo pensar en una serie de soluciones posibles para el problema más general donde los rangos no son uniformes y hay “agujeros”. Los más simples son:

  1. Simplemente rellene un Mapa para todos los valores de clave válidos, con la asignación de varias teclas al mismo valor. Suponiendo que usa HashMaps, esta debería ser la más eficiente en tiempo (búsquedas O (1)), aunque tiene más trabajo en el momento de la configuración y usa más espacio.
  2. Use un NavigableMap y use floorEntry(key) para hacer las búsquedas. Esto debería ser menos eficiente en el tiempo (O (log (N) búsquedas) pero más eficiente en el uso del espacio.

Aquí hay una solución que usa NavigableMaps que permite ‘agujeros’ en la asignación.

 private static class Range { public int upper, value; ... } NavigableMap map = new TreeMap(); 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 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 } 

Por otro lado, si no hay 'agujeros' la solución es más simple:

 NavigableMap map = new TreeMap(); 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-código:

  1. Almacene los límites del rango en una matriz plana: new int[] {0, 3, 5, 15, 100, 300} .
  2. Búsqueda binaria a través de la matriz como si insertara un número en la matriz. Ver Arrays.binarySearch() .
  3. Si el punto de inserción es par, el número no encaja en ningún rango.
  4. Si el punto de inserción es impar, cabe en el rango correspondiente. Por ejemplo, el punto de inserción para 10 en la matriz anterior sería 3 , colocándolo entre 5 y 15 , por lo que pertenece al segundo rango.

En un caso más general que no se puede resolver con aritmética, puede crear un TreeMap con un Comparador apropiado. Agregue asignaciones para los valores de frontera y luego use ceilingEntry o floorEntry para encontrar la coincidencia adecuada.

Creo que lo que quieres es algo parecido a foo()/10 , pero eso te dará rangos levemente diferentes a los que pediste. Siempre puede hacer comparaciones con los dos puntos finales para cada elemento en su “mapa” si no siguen un patrón fácil.

Creo que la solución más fácil sería agregar asignaciones desde los límites superiores de sus rangos hasta el valor al que se asigna el rango, y simplemente seguir incrementando su número (clave en el mapa) hasta llegar a un mapeo (que es el límite superior para el rango en el que está tu número).

Otra forma sería rellenar el mapa con todas las entradas de un rango y agregar una asignación para cada una.

Cuál es más eficiente depende de si es probable que necesite solicitar todos los números en un rango repetidamente (use la última solución), o solo algunos de los números varias veces (use el primero)