技术上讲,对于双向链表二分查找的运行时间是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) 的工作来自于遍历链表而不是做比较。