Использование 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

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

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

Здесь используется решение с использованием NavigableMaps, которое позволяет "дыры" в отображении.

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
}

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

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

Ответ 2

Псевдо-код:

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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