упорядоченный поиск по двусвязному списку

Question

предположим, что у нас есть двусвязный список, упорядоченный по целому значению:

struct ListItem
{
  int value;
  ListItem *prev, *next;
};

struct List
{
  ListItem *first, *last;
  int count;
};

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

Answer 1

Для большинства практических целей нет.Если вы хотите более быстрый поиск, связанный список - плохой выбор структуры данных.Вместо этого рассмотрим вектор, deque, set или multiset.

Редактировать: Возможно, было бы хорошо дать некоторые рекомендации о том, какой из них имеет смысл, когда.Вектор имеет смысл, если у вас есть две в основном отдельные фазы: либо вы вставляете все свои данные по порядку, либо вставляете и сортируете, затем после сортировки данные остаются статичными, и вы просто выполняете поиск в них.Deque почти такой же, за исключением того, что вы можете вставить его с любого конца, поэтому, если вы можете получить данные не по порядку, но новые данные всегда принадлежат одному концу коллекции или другому, это может быть хорошим выбором.

A set или multiset работает лучше, если вы собираетесь смешивать вставки / удаления с поисками.Он постоянно сортируется, поэтому поиск всегда выполняется достаточно быстро.Между двумя (набор против мультимножества) выбор довольно прост: если вам нужно убедиться, что каждый элемент в коллекции уникален, вы хотите установить.Если у вас может быть несколько элементов с одним и тем же ключом, вам нужен мультимножество.

Answer 2

Да, вы можете, но если операция «сравнивать значения» намного дороже, чем «указатель перемещения», это не имеет никакого смысла.Поскольку обычно «перемещение» обходится примерно так же дорого, как и «сравнение», при обычном поиске:

• O (N) перемещений
• O (N) сравнений

с двоичным кодом:

• O (N) перемещается, чтобы определить размер списка
• O (N) перемещается, чтобы найти элемент
• O (log (N)) сравнения.

В вашем примере значение равно "int", что означает, что сравнение даже дешевле, чем перемещение, поэтому двоичный алгоритм будет намного дороже.

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

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

Answer 3

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

Answer 4

Если вам нужно выполнить поиск только пару раз, я подозреваю, что поиск по списку от начала до конца будет лучшим выбором.Могут быть некоторые алгоритмы, которые могут быть более эффективными, но это будет лишь немного лучше.

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

Answer 5

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