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