mapa java para el rango busca

Question

que tienen un caso de uso en el que si un número está entre 0-10 debe devolver 0 y si se encuentra entre 11-20 se 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 mapas java, pero no permite rango buscar

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

int foo() { 

} 

si foo devuelve 5, ya que se encuentra entre 0 t o 10 usaría 0, si foo de retorno 25 que usaría 2.

Cualquier idea

Edit: 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. Basado en las consultas que he agregado el ejemplo correcto, los números son continuos

Answer 1

Puedo pensar en una serie de posibles soluciones 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. Utilice un NavigableMap y use floorEntry(key) para realizar las búsquedas. Esto debería ser menos eficiente en el tiempo O (log (N) operaciones de búsqueda() pero más eficiente del espacio.

Aquí hay una solución utilizando NavigableMaps que permite 'agujeros' en el mapeo.

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 
} 

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

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

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

Answer 3

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.

Answer 4

Pseudo-código:

1. Almacena 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 se 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.

Answer 5

Creo que la solución más fácil sería agregar asignaciones de los límites superiores de sus rangos al valor al que se asigna, y 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 se encuentra su 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 necesita para solicitar todos los números en un rango repetidamente (utilizar la última solución), o sólo algunos de los números de un par de veces (usar la primera)