Почему двоичный поиск в списке в Java?

Question

Я не уверен, почему List как общая структура данных должен иметь алгоритм двоичного поиска, если список отсортирован. Разве метод get, который принимает индекс, не пересекает список последовательно, по крайней мере, для подтипа List LinkedList? Если это так, я не вижу никаких преимуществ использования двоичного поиска по сравнению с последовательным сравнением для LinkedList. Конечно, если мы не ограничим List значением ArrayList, мы сможем выполнить двоичный поиск с большей уверенностью.

Правильно ли мое понимание? Спасибо.

Answer 1

Существует множество способов реализации List.В стандартных библиотеках Java есть ArrayList, LinkedList, CopyOnWriteArrayList и т. Д., А также множество других реализаций, помимо этих ( VLists , циклические буферы, асимметричные списки биномов, расширяемые массивы, 2-3 пальца и т. Д.).Идея обеспечения бинарного поиска заключается в том, что, хотя не все реализации List поддерживают произвольный доступ, тем, кому это действительно нужно, было бы полезно иметь общую реализацию бинарного поиска, чтобы авторам каждой структуры данных не приходилось переопределять ее с нуля.Например, если я реализую сумасшедшую новую структуру списка, которая поддерживает произвольный доступ, если я реализую интерфейс List, я могу автоматически получать двоичный поиск, доступный из класса Collections.

Интересно, что метод binarySearch написантакой, что он смотрит на тип List и видит, реализует ли он интерфейс RandomAccess, прежде чем он фактически выполняет бинарный поиск.Если в списке не реализовано RandomAccess, вместо стандартного двоичного поиска метод использует модифицированный двоичный поиск с итераторами, который гарантированно выполнит не более O (n) итераций и O (log n) сравнений.Идея состоит в том, чтобы отслеживать, где приземлился последний зонд, затем идти вперед или назад на соответствующее количество шагов, чтобы найти следующее местоположение зонда, и т. Д. Тогда полная работа будет не более n / 2 + n / 4 + n/ 8 + n / 16 + ... = 2n, так что в худшем случае это только вдвое хуже, чем при линейном поиске в худшем случае.

Короче говоря, предоставление общей реализации binarySearchНе всегда можно быстро найти что-то в Списке, но для структур, которые поддерживают быстрый доступ, это может иметь огромное значение и сэкономить много времени для разработчиков.Кроме того, постепенное ухудшение модифицированного бинарного поиска, выполняемого за время O (n), означает, что реализация никогда не будет намного хуже, чем стандартное линейное сканирование.

Это рассуждение аналогичнообоснование разработки алгоритмов C ++, которые работают с общими диапазонами значений.Эффективность этих алгоритмов может быть намного хуже, чем у специализированной версии алгоритма для каждой структуры данных, но наличие общей версии означает, что любые новые контейнеры, поддерживающие итераторы, могут автоматически иметь множество функциональных возможностей, помимо того, чтоуказано в интерфейсе.

Надеюсь, это поможет!

Answer 2

Да, вы правы, если список не обеспечивает произвольный доступ, как в случае с LinkedList, никаких преимуществ нет. От Javadoc Collections.binarySearch():

Этот метод выполняется за время log (n) для списка «произвольного доступа» (который обеспечивает позиционный доступ почти в постоянное время). Если указанный список не реализует интерфейс {@link RandomAccess} и имеет большой размер, этот метод будет выполнять двоичный поиск на основе итератора, который выполняет O (n) обход ссылок и O (log n) сравнения элементов.

Итак, сложность в этом случае будет такой же, как и в случае последовательного сравнения - O (n). Практически я считаю, что последовательное сравнение может быть быстрее во многих случаях.