Использование java-карты для поиска диапазона

У меня есть прецедент, где, если число лежит между 0-10, оно должно возвращать 0, а если оно лежит между 11-20, оно должно возвращать 1 и т. Д.

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) 

Я думал, как я могу реализовать и думать о java-картах, но это не позволяет искать диапазон

Меня интересует что-то вроде этого, у меня есть функция

 int foo() { } 

если foo возвращает 5, так как он лежит между 0 и 10, я бы использовал 0, если foo return 25 использовал бы 2.

Есть идеи

Изменить: на самом деле диапазоны не такие простые, как 0-10, 11-20. Я хочу иметь возможность выполнять поиск по диапазону. Прошу прощения за путаницу. Основываясь на запросах, я добавил правильный пример: числа непрерывны

Я могу придумать ряд возможных решений для более общей проблемы, когда диапазоны неравномерны и есть «дырки». Самые простые:

  1. Просто заполните карту для всех допустимых значений ключа, с сопоставлением нескольких ключей с тем же значением. Предполагая, что вы используете HashMaps, это должен быть самый эффективный (O (1) поиск), хотя у вас больше времени на настройку, и вы используете больше места.
  2. Используйте floorEntry(key) и используйте floorEntry(key) для поиска. Это должно быть менее эффективным (O (log (N) поиск), но более эффективное пространство.

Вот решение, использующее NavigableMaps, которое позволяет «дыры» в отображении.

 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 } 

С другой стороны, если нет «дырок», решение проще:

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

Псевдо-код:

  1. Сохраните границы диапазона в плоском массиве: new int[] {0, 3, 5, 15, 100, 300} .
  2. Двоичный поиск по массиву, как будто вставка числа в массив. См. Arrays.binarySearch() .
  3. Если точка вставки четная, номер не помещается в любой диапазон.
  4. Если точка ввода нечетна, она вписывается в соответствующий диапазон. Например, точка вставки для 10 в вышеприведенной матрице будет равна 3 , помещая ее между 5 и 15 , поэтому она принадлежит во втором диапазоне.

В более общем случае, который не может быть решен с помощью арифметики, вы можете создать TreeMap с соответствующим компаратором. Добавьте сопоставления для граничных значений, а затем используйте функцию потолочной обработки или floorEntry, чтобы найти соответствующее совпадение.

Я думаю, что вы хотите что-то вроде линий foo()/10 , но это даст вам диапазоны немного от того, что вы просили. Вы всегда можете просто сравнивать с двумя конечными точками для каждого элемента вашей «карты», если они не соответствуют простому шаблону.

Я думаю, что самым простым решением было бы добавлять отображения из верхних границ ваших диапазонов в значение, которое соответствует картам, и просто увеличивать ваш номер (ключ на карте) до тех пор, пока вы не достигнете сопоставления (которое является верхней границей для диапазон вашего номера).

Другой способ – заполнить карту всеми элементами в диапазоне и добавить отображение для каждого.

Какой из них более эффективен, зависит от того, вероятно, вам нужно повторно запрашивать все числа в диапазоне неоднократно (используйте последнее решение) или просто некоторые числа несколько раз (используйте первый)

Давайте будем гением компьютера.