Существует ли какой-либо алгоритм бинарного поиска в отсортированном связанном списке? Или это полезно каким-то образом? Я знаю, что в массиве очень эффективно использовать двоичный поиск, поскольку мы знаем адрес всех элементов. Но в связанном списке мы должны проходить через каждый узел.Бинарный поиск в связанном списке
Причина использования двоичного поиска - найти номер в o (log n). Однако связанный список невозможен. Предлагается использование дерева или массива. Посмотрите на это:
how to apply binary search O(log n) on a sorted linked list?
В Linked List, бинарный поиск может не достичь сложности O (журнал N), как описано (Luck @ Хорошие), но не менее может быть достигнуто немного с помощью Double Метод указателя (при условии, что Связанный список находится в отсортированном порядке), как описано здесь в этой работе: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
Вы можете сделать что-то подобное в списке пропуска - https://en.wikipedia.org/wiki/Skip_list - но не в нормальном связанном списке. –
Возможный дубликат [как применить двоичный поиск O (log n) в отсортированном связанном списке?] (Http://stackoverflow.com/questions/5281053/how-to-apply-binary-search-olog-n-on -a отсортированный-связанный список) –