如何在O(n)时间内对双向链表进行二进制搜索？

Question

我听说可以在O(n)时间内实现双向链表上的二进制搜索。访问双向链表的随机元素需要O(n)时间，而二进制搜索访问O(log )个不同的元素，所以运行时不应该是O( n )吗？

Answer 1

说双向链表上的二进制搜索的运行时间是O(n log n)在技术上是正确的，但这并不是一个严格的上限。使用二进制搜索的稍微更好的实现和更聪明的分析，可以使二进制搜索在O(n)时间内运行。

二进制搜索背后的基本思想如下：

• 如果列表为空，则要搜索的元素不会返回中间元素。
• 如果匹配有问题的元素，则返回该元素。
• 如果该元素比有问题的元素大，则丢弃列表的后半部分。

<>H111>如果它比有问题的元素小，则丢弃列表的前半部分

​

双向链表上二进制搜索的一个简单实现是计算索引以查找每次迭代(就像数组中的情况一样)，然后从列表的前端开始访问每个迭代，并向前扫描适当数量的步骤。这确实非常慢。如果要搜索的元素位于数组的末尾，则查找的索引将是n/2、3n/4、7n/8等。

对数n/2+ 3n/4 + 7n/8 + 15n/16 + ... (Θ(

n)项)

对数n/2+n/2+ ... +n/2(Θ(≥n)项)

=Θ(n log n)

和

对数n/2+ 3n/4 + 7n/8 + 15n/16 + ... (Θ(

n)项)

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

=Θ(n log n)

因此，该算法的最坏情况时间复杂度为Θ( n )。

但是，我们可以通过更聪明的方法来将此速度提高一个对数(Θ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 +…因此，在最坏情况下完成的总功只有Θ( n)，这比之前的Θ(n )最坏情况要好得多。

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