Можно ли применить бинарный поиск к списку ссылок, чтобы найти элемент?

Question

Я прочитал вопрос, возможно ли применить бинарный поиск в списке ссылок?

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

Answer 1

Основная проблема, кроме того, что у вас нет постоянного доступа к связанным элементам списка, заключается в том, что у вас нет информации о длине списка.В этом случае у вас просто нет возможности «разрезать» список на 2 половины.

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

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

Answer 2

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

Если вам нужен быстрый поиск, древовидные структуры данных (дерево R / Btrie, heap и т. д.) предлагают множество преимуществ связанного списка (относительно дешевая случайная вставка / удаление), но при этом очень эффективны при поиске.

Answer 3

для применения бинарного поиска в связанном списке, вы можете вести подсчет переменной, который должен выполнять итерацию по связанному списку и возвращать общее количество узлов. Также вам нужно будет сохранить переменную типа int, скажем, INDEX в вашем классе узлов, которая должна увеличиваться при создании каждого нового узла. после чего вам будет легко разделить связанный список на две половины и применить к нему бинарный поиск.

Answer 4

По моему мнению, нет возможности искать связанный список в режиме бинарного поиска.В бинарном поиске мы обычно выявляем «среднее» значение массива, что невозможно со списками, поскольку списки - это структура, в которой мы должны строго использовать «начало» (узел, указывающий на самый 1-й узел списка) для перехода к любому изнаш список элементов.

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

Итак, я думаю, что бинарный поиск невозможен со связанным списком в обычной практике.

Answer 5

Вы можете выполнить бинарный поиск по связанному списку. Как вы говорите, у вас нет произвольного доступа, но вы все равно можете найти элемент с определенным индексом, начиная с начала списка или с какой-то другой позиции. Таким образом, прямой двоичный поиск возможен, но медленнее по сравнению с двоичным поиском в массиве.

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

Answer 6

Однажды я реализовал нечто подобное для односвязного списка, содержащего отсортированные ключи.Мне нужно было найти в нем несколько ключей (зная только один из них в начале, остальные зависели от него), и я хотел избегать обхода списка снова и снова.И я не знал длины списка.

Итак, я закончил тем, что сделал это ... Я создал 256 указателей, чтобы указывать на элементы списка, и заставил их указывать на первые 256 элементов списка.Как только все 256 были использованы и 257-й требовался, я отбросил значения нечетных указателей (1,3,5 и т. Д.), Сжал четные (0,2,4 и т. Д.) В первые 128 указателейи продолжал присваивать оставшуюся половину (128) указателей остальным, на этот раз пропуская каждый второй элемент списка.Этот процесс повторялся до конца списка, после чего эти указатели указывали на элементы, равномерно распределенные по всему списку.Затем я мог бы выполнить простой двоичный поиск, используя эти 256 (или меньше) указателей, чтобы сократить поиск по линейному списку до 1/256-й (или 1 / независимо от-го) от первоначальной длины списка.причудливый или мощный, но иногда может быть достаточным улучшением с небольшими изменениями кода.

Answer 7

Не с классическим связанным списком по указанным вами причинам.

Но есть структура, которая допускает форму двоичного поиска, полученную из связанных списков: Пропуск списков .

(Это не тривиально для реализации.)