有序双向链表搜索

Question

假设我们有一个按整数值排序的双向链表：

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

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

我们能否使用更快的搜索算法，比如二分查找，来定位 List 中的 ListItem，应该怎么做呢？

- Muhammad

---

听起来像是作业。请添加作业标签和/或在标题中加上“作业”这个词。 - Cheers and hth. - Alf

编写多语言源文件很困难。我建议你坚持使用C或C++中的一种。 - pmg

Answer 1

对于大多数实际用途而言，不是。如果您想要更快的搜索，则链表是一种较差的数据结构选择。相反，考虑使用矢量、双端队列、集合或多重集。

编辑：也许提供一些关于这些选项何时使用有帮助的指导会很好。如果您有两个基本分离的阶段（即将所有数据按顺序插入，或者先插入和排序，然后在数据排序后，数据保持静态，并且只在其中进行搜索），则矢量是最合适的选择。双端队列基本上是相同的，只是您可以在任意一端插入，因此如果您可能得到无序数据，但新数据始终属于集合的一端，则它可能是一个不错的选择。

如果您要混合插入/删除和查找，则set或multiset效果更好。它始终保持排序，因此搜索始终是相当快的。在set和multiset之间，选择相当简单：如果您需要确保集合中的每个项目都是唯一的，则要使用set。如果可能具有具有相同键的多个项，则应该使用multiset。

- Jerry Coffin

---

我正在为大数据集编写哈希表，该哈希表使用分离链接法，并且使用向量将是一个糟糕的选择，因为需要进行内存重新分配。 - Muhammad

@Muhammad：我不确定我理解内存重新分配如何在这种情况下产生很大的差异。无论如何，对于哈希表，您搜索冲突链的方法应该很少有太大的区别。除非是病态哈希函数或者对整体大小的猜测极其不正确，否则你很少会搜索超过几个项目（通常约为3个）。在这么小的搜索集合中，线性搜索和二进制搜索几乎没有任何区别。 - Jerry Coffin

Answer 2

如果节点之间没有基于其值的排序，那么别无选择，只能逐个检查所有节点。因此时间复杂度为O(n)。

- S..K

Answer 3

可以，但是除非“比较值”的操作比“移动指针”显然要昂贵得多，否则完全没有意义。由于通常“移动”和“比较”的代价大致相当，因此在普通搜索中：

• O(N) 移动
• O(N) 比较

用二进制查找：

• O(N) 移动以确定列表的大小
• O(N) 移动以定位元素
• O(log(N)) 比较。

在您的示例中，值为“int”，这意味着比较甚至比移动更便宜，因此二进制算法的成本会高得多。

如果您知道列表的大小，则二进制可能会（可以说）更便宜，但双向逻辑遍历和元素计数的增加复杂性将抵消减少的值比较数量带来的任何好处。

当然，如果您需要多次搜索，最简单的方法就是将链表转换为数组或创建索引-指针数组。如果值比int更复杂且更难比较，当然最快的算法是最理想的。

- SF.

Answer 4

好的，你仍然需要循环遍历所有元素直到中间元素。我不确定二分查找是否会加速对链表的搜索，因为这个原因。例如，在元素位于中间元素之前的情况下，逻辑上只需循环遍历这些元素似乎更快。否则，您将只是去到中间，看看您的元素与其的关系，然后再次循环，是的...循环是真正会导致效率低下的地方。我想这也取决于您的元素在列表中确切的位置。

- MGZero

Answer 5

如果您只需要执行几次搜索，我认为从头到尾遍历列表是最好的选择。可能有一些更有效的算法，但效率只会略微提高。

然而，如果您需要多次执行搜索，则将列表复制到支持二分搜索的有序随机访问容器中是最好的选择。

- Nubcase