Блог

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

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

У кого-нибудь есть какой-нибудь способ сделать это?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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