algorithm - 如何在 O(n) 时间内对双向链表进行二分查找？

Question

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

Answer 1

从技术上讲，双向链表的二分查找运行时间是 O(n log n)，但这并不是严格的上限。使用稍微更好的二分搜索实现和更巧妙的分析，可以使二分搜索在时间 O(n) 内运行。

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

• 如果列表为空，则表示要搜索的元素不存在。
• 否则:
  • 查看中间元素。
  • 如果它匹配有问题的元素，则返回它。
  • 如果它比有问题的元素大，则丢弃列表的后半部分。
  • 如果它小于所讨论的元素，则丢弃列表的前半部分。

在双向链表上简单地实现二分查找的方法是计算索引以在每次迭代中查找(就像在数组情况下一样)，然后通过从列表的前面开始并扫描来访问每个索引前进适当的步数。这确实很慢。如果要搜索的元素在数组的最末端，则查找的索引将是 n/2、3n/4、7n/8 等。总结最坏情况下所做的工作，我们得到

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) terms)

≥ n / 2 + n / 2 + ... + n / 2 (Θ(log n) terms)

= Θ(n log n)

和

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) terms)

≤ n + n + ... + n (Θ(log n) terms)

= Θ(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 + ...)

≤ n

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

最后一个细节:您为什么要这样做？毕竟，在双向链表中搜索元素已经花费了 O(n) 的时间。这种方法的一个主要优点是即使运行时间是 O(n)，我们最终只进行了 O(log n) 次总比较(二分查找的每一步一次)。这意味着如果比较开销很大，我们最终可能会使用二分搜索比使用普通线性搜索做更少的工作，因为 O(n) 来自遍历列表的工作而不是进行比较的工作。