как применить бинарный поиск O (log n) в отсортированном связанном списке?

Question

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

Сложность времени не должна превышать O(log n). Кажется, нам нужно применить бинарный поиск в этом связанном списке. Как? Поскольку связанный список не обеспечивает произвольный доступ, если мы попытаемся применить алгоритм двоичного поиска, он достигнет O (n), так как нам нужно найти длину списка и перейти к середине.

Есть идеи?

Answer 1

Это невозможно при использовании простого односвязного списка.

Эскизное доказательство: чтобы исследовать последний узел односвязного списка, мы должны выполнить n-1 операции следования за "следующим" указателем [доказательство по индукции о том, что существует только одна ссылка на k+1 th узел, и он находится в k th узле, и для его выполнения требуется операция]. Для определенных входных данных необходимо проверить последний узел (в частности, если искомый элемент равен или превышает его значение). Следовательно, для определенных входов требуемое время пропорционально n.

Вам нужно больше времени или другая структура данных.

Обратите внимание, что вы можете сделать это в O (log n) Сравнение с двоичным поиском. Это займет больше времени , чем это, так что этот факт представляет интерес, только если сравнение намного дороже, чем обход списка.

Answer 2

Вам необходимо использовать Пропустить список .Это невозможно с обычным связанным списком (и я действительно хочу узнать, возможно ли это с обычным списком).

Answer 3

В связанном списке бинарный поиск может не достигать сложности O (log n), но наименьшего можно достичь с помощью метода двойного указателя, как описано здесь в этой исследовательской работе: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf

Answer 4

Да, это возможно на языке Java, как показано ниже ..

Collections.<T>binarySearch(List<T> list, T key)

для бинарного поиска по любому List. Он работает на ArrayList и LinkedList и на любом другом List.

Answer 5

Как уже отмечалось, это в общем случае невозможно. Однако в таком языке, как C, если узлы списка расположены непрерывно, можно было бы рассматривать структуру как массив узлов.

Очевидно, что это только ответ на вариант вопроса с подвохом, но проблема всегда невозможна или вопрос с подвохом.

Answer 6

Используйте MAPS для создания LINK LISTS.
Карта M, M [первый элемент] = второй элемент, M [второй элемент] = третий элемент,
...
...
егосвязанный список ...
а потому что это карта ...
, которая внутренне использует бинарный поиск для поиска любого элемента ..
любой поиск элементов займет O (log n)