Прочитав этот вопрос и ответы на него, я пришел к выводу, что нет стандартных реализаций этих двух алгоритмов. Сначала немного истории:
Большинство из нас знакомы с binarySearch . Идея состоит в том, что, учитывая отсортированный массив (или Collection, если использовать поиск из этого класса), он эффективно (в логарифмическом - O (log 2 n) время) находит позицию данного элемента в массиве / коллекции. Конкретная ссылка, которую я предоставил, состоит из следующей документации:
[...] Если массив содержит несколько элементов с указанным значением, нет гарантии, какой из них будет найден.
Иногда нам все равно, нашли ли мы (или не смогли найти) первое или последнее вхождение интересующего нас элемента. Но что, если нам все равно все равно?
Если мы заботимся, мы используем варианты бинарного поиска, называемые нижняя граница и верхняя граница . Они возвращают первое и последнее 1 вхождение данного элемента соответственно.
Я из C++, и мне очень нравится тот факт, что я могу использовать std::lower_bound и std::upper_bound (и их версии функций-членов для контейнеров, которые поддерживают порядок, например, std::map или std::set) для контейнеров .
Простейший вариант использования, учитывая отсортированную коллекцию, определяет, сколько элементов равно x. Этот ответ на вопрос, который я первоначально связал, содержит следующее:
[После выполнения бинарного поиска] Затем продолжите линейную итерацию, пока не дойдете до конца равного диапазона.
Проблема заключается в том, что эта операция является линейной, и для коллекций со случайным доступом мы можем сделать намного лучше - мы можем использовать нижнюю границу и верхнюю границу, затем вычесть возвращенные индексы и получим результат в логарифмическом, а не в линейный, время.
По сути, меня удивляет, что в Java не может быть реализовано алгоритмов с верхними и нижними границами. Я понимаю, что могу легко реализовать их самостоятельно, но, например, что если мои данные хранятся в TreeMap или TreeSet? Они не имеют произвольного доступа, но, учитывая их реализацию, верхние и нижние границы могут быть легко реализованы как их методы.
Наконец, мой вопрос - есть ли реализации верхней и / или нижней границы в Java, предпочтительно эффективные в отношении TreeSet и TreeMap?
1 Хотя это зависит от соглашения. В C++ верхняя граница возвращает первый элемент, который на больше , чем искомый элемент.