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

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

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

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

在双链表上进行二进制搜索的一个简单实现是通过计算索引来查找每个迭代(就像在数组的情况下一样),然后从列表的前面开始并向前扫描适当数量的步骤来访问每个迭代。这确实非常缓慢。如果要搜索的元素位于数组的最末端,则查找的索引将是n/2、3n/4、7n/8等。将在最坏情况下所做的工作相加,我们得到

n/2+3n/4+7n/8+15n/16+。。。(θ(logn)项)

≥n/2+n/2+…+n/2(θ(logn)项)

=θ(n对数n)

和

n/2+3n/4+7n/8+15n/16+。。。(θ(logn)项)

≤n+n+…+n(θ(logn)项)

=θ(n对数n)

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

然而,我们可以通过更巧妙的方法将速度提高一倍,即θ(logn)。前面的算法之所以慢,是因为每次我们需要查找元素时,我们都从数组的开头开始搜索。然而,我们不需要这样做。第一次查找中间的元素后,我们已经在数组的中间了,我们知道下一次查找将在位置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(logn)个总比较(二进制搜索的每一步一个)。这意味着,如果比较代价高昂,我们最终可能会使用二进制搜索比使用普通线性搜索做更少的工作,因为O(n)来自于在列表中遍历所做的工作,而不是进行比较的工作。