java - 搜索排序的链表时，二进制或顺序/线性搜索是否更有效？

Question

我需要编写一个程序来搜索以前排序的链表，但我不确定哪种搜索更有效。

Answer 1

链表的所有遍历都是有序的，因此线性搜索是您能做的最好的事情，平均情况与元素数量呈线性关系。如果要进行大量搜索并且您仍然需要一个链表（而不是像数组这样的随机访问结构），请考虑使用跳过列表，它可以让您向前跳过直到靠近所需的元素。

Answer 2

线性搜索会更有效，这就是原因。

为了到达大小为n的双向链表中的第 k 个位置，您必须迭代最多 n/2 个元素。

如果您要在此之上应用二分搜索，那么您最终将不得不每次都向下搜索k个元素，再加上执行二分搜索的工作。

O(n + log(n)) = O(n)，相当于线性搜索的性能。

Answer 3

如果您的比较便宜，那么其他答案是正确的，即线性搜索和二进制搜索大多是等效的（二进制搜索的预期节点遍历数略高，尽管 big-O 是相同的O(n)遍历）。

但这假设比较相对于遍历的成本可以忽略不计。这并不总是一个好的假设。如果您的比较很昂贵，那么二进制搜索仍然值得，因为二进制搜索仍然O(log n)是比较次数，而线性搜索是O(n). 例如，如果您的比较操作非常昂贵（例如，文件数据的 MD5 哈希，并且您没有出于任何原因将其与文件名一起缓存），并且您有一个 1000 元素列表，线性搜索意味着平均而言，您正在计算 500 个文件的 MD5 哈希（在这种情况下，您可以通过根据您要搜索的 MD5 是否以0-7or开头来选择结尾来减少它8-f，但即便如此， 它的O(n)比较除以一个常数因子）。二进制搜索意味着最多 10 个（或 11 个，不会被一个错误所困扰）文件读取和 MD5 计算。如果文件足够大，这就是运行约 1 秒和约 50 秒之间的差异。