如何在双向链表上实现O(n)时间复杂度的二分查找？

Question

我听说可以在O(n)时间内在双向链表上实现二分查找。在双向链表中访问一个随机元素需要O(n)的时间，并且二分查找访问O(log n)个不同的元素，那么运行时间不应该是O(n log n)吗？

- templatetypedef

---

你可以用O(n)的时间复杂度进行线性搜索，那么为什么要使用需要O(nlogn)或其他超过O(n)的算法进行二分查找呢？在定义了一个基于包（非集合，如数组或链表）的抽象API中，如果有一个BinarySearch方法，那么应该将其实现为链表版本的线性搜索...调用者无法确定使用了哪种算法，只能通过计时并检查它是否实际上是一个毫无意义的缓慢二分查找来判断。实际上，对于链表的二分查找可以通过线性搜索以O(n)的时间复杂度来实现...名称并不代表它实际上所做的事情。 - Jim Balter

优点在于，虽然它需要O(n)的工作来遍历列表，但只进行了O(log n)次比较。如果列表中存储了巨大的元素，则这可能比进行线性搜索要快得多。 - templatetypedef

好的，说得对...我现在已经看完了你对问题的回答。语句“在双向链表上运行二分查找的时间复杂度为O(n log n)”是错误的，因为你自己提供了一个具有O(n)算法和O(logn)比较的结果。所以你在问题中听到的话是正确的……“可以在O(n)时间内在双向链表上实现二分查找”……你应该修正你答案顶部的声明。无论如何，感谢你提供算法和分析..我一直在寻找它。 - Jim Balter

PS：它也适用于单链表，因为您始终拥有两个子列表的头部，并且可以使用Floyd的乌龟和兔子技巧（https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/）找到中点。 - Jim Balter

事实上，声称二分查找需要 O(n log n) 时间并不是错误的。只是这个上限不够紧确。例如，我声称我最多有 1 千米高，虽然实际上我的身高要明显低于这个数字。另外，感谢分享那个链接！我还在另一个问题帖子中介绍了该算法的详细信息。 - templatetypedef

Answer 1

技术上讲，对于双向链表二分查找的运行时间是O(n log n)，但这并不是一个紧密的上界。通过使用稍微更好的二分查找实现和更聪明的分析，可以将二分查找运行时间优化到O(n)。

二分查找的基本思想如下：

如果列表为空，则搜索的元素不存在。 否则： 查看中间元素。 如果与要查找的元素匹配，则返回它。 如果大于要查找的元素，则舍弃后半部分列表。 如果小于要查找的元素，则舍弃前半部分列表。

双向链表二分查找的简单实现会在每次迭代中计算要查询的索引（就像在数组情况下一样），然后从列表的开头开始扫描适当数量的步骤以访问每个索引。这确实非常慢。如果要查找的元素位于数组末尾，那么查找的索引将是n/2、3n/4、7n/8等。在最坏情况下总的工作量为：

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n)个项) ≥ n / 2 + n / 2 + ... + n / 2 (Θ(log n)个项) = Θ(n log n)

和

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n)个项) ≤ n + n + ... + n (Θ(log n)个项) = Θ(n log n)

因此，该算法的最坏时间复杂度为Θ(n log n)。然而，我们可以通过更聪明的方法把算法速度加快一个 Θ(log n) 倍。之前的算法慢是因为每次查找元素都需要从数组开头开始查找。但是，我们其实不需要这么做。在第一次查找中间元素后，我们已经在数组的中间了，并且我们知道下一次查找将会在位置 n / 4 或 3n / 4，距离我们上次停下的位置只有 n / 4 的距离（相比于从数组开头开始的 n / 4 或 3n / 4 的距离）。如果我们直接从停下的位置（n / 2）出发去下一个位置，而不是重新在列表开头开始搜索，会怎样呢？

以下是新算法的步骤：先扫描到数组的中间，需要 n / 2 步。然后，确定是要访问数组的前半段的中间元素还是后半段的中间元素。从位置 n / 2 出发到达那里只需要总共 n / 4 步。从那里出发到包含元素的四分之一的数组的中点只需要 n / 8 步，然后从那里到包含元素的八分之一的数组的中点只需要 n / 16 步，以此类推。这意味着总步数可以表示为：

n / 2 + n / 4 + n / 8 + n / 16 + ...

≤ n

这是因为无限几何级数1/2 + 1/4 + 1/8 + ...的和是1。因此，在最坏情况下，总共的工作量只有 Θ(n)，比之前的 Θ(n log n) 要好得多。

最后一个细节: 为什么你会这样做呢？ 毕竟，使用双向链表搜索元素已经需要 O(n) 的时间了。这种方法的一个主要优点是，尽管运行时间是 O(n)，但我们只需要执行 O(log n) 次比较（每个二分查找步骤一次）。这意味着如果比较操作很昂贵，使用二分查找可能比使用普通线性搜索更省事，因为 O(n) 的工作来自于遍历链表而不是做比较。

- templatetypedef