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

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

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

Любые идеи?

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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