Поиск наименьшего элемента в списке после некоторого значения

Question

Рассмотрим список целых чисел <1,5,10> (предположим, отсортировано по возрастанию).

Имеется ли целое число, скажем, key = 6, есть ли служебный метод, который возвращает наименьший элемент после key (в этом случае это будет 10)?

Примечание: циклический просмотр элементов списка и сравнение его с key - очевидный способ сделать это, но мне просто интересно, существует ли утилитаспособ сделать то же самое:)

Answer 1

Рассматривали ли вы Бинарный поиск ? Коллекции имеет метод binarySearch, который вы можете использовать.

Из документации по коллекциям binarySearch:

Возвращает:

индекс ключа поиска, если он содержится в списке;в противном случае (- (точка вставки) - 1).Точка вставки определяется как точка, в которой ключ будет вставлен в список: индекс первого элемента больше, чем ключ, или list.size (), если все элементы в списке меньше указанного ключа.Обратите внимание, что это гарантирует, что возвращаемое значение будет> = 0 тогда и только тогда, когда ключ найден.

Я позволю вам выяснить, как можно использовать возвращаемое значение Collections.binarySearch для полученияответ вам нужен.

Answer 2

Двоичный поиск работает, но если на самом деле у вас есть отсортированный набор значений, то вместо List, SortedSet (или даже лучше NavigableSet), является наиболее естественной структурой данных для выбора.

Вот пример использования:

    NavigableSet<Integer> nums = new TreeSet<Integer>(
        Arrays.asList(9,1,5,7,3)
    );

    System.out.println(nums); // "[1, 3, 5, 7, 9]"

    System.out.println(nums.first()); // "1"
    System.out.println(nums.last());  // "9"

    System.out.println(nums.higher(3)); // "5"
    System.out.println(nums.lower(8));  // "7"

    System.out.println(nums.subSet(2,8)); // "[3, 5, 7]"
    System.out.println(nums.subSet(1, true, 5, true));  // "[1, 3, 5]"

Также есть NavigableMap аналог, который может быть еще более полезнымв некоторых сценариях.