在双向链表上执行Θ(log n)时间复杂度的二分查找是否可行？

答案是否定的，你提到的观点存在明显错误。

核心原因 #

二分查找能达到Θ(log n)时间复杂度的核心前提是支持O(1)时间的随机访问，可以直接定位到查找区间的中间元素：

• 数组类结构的元素在内存中连续存储，通过下标偏移就能直接获取中间元素，符合这个前提
• 标准双向链表的节点是离散存储的，每个节点仅持有前驱、后继节点的指针，没有随机访问能力

哪怕双向链表本身是完全有序的，你要获取任意区间的中间节点，都需要从区间的头/尾节点开始遍历半段区间才能找到，单这一步的时间复杂度就达到了Θ(k)（k为当前区间的长度）。

总时间复杂度计算 #

完整执行一次二分查找的总耗时是每一轮查找中间节点的耗时之和：
Θ(n/2 + n/4 + n/8 + ... + 1) = Θ(n)

这个复杂度和普通的顺序遍历查找完全是同一量级，甚至因为多了区间边界判断、节点跳转的额外开销，实际运行效率还不如直接从头到尾遍历查找。

补充说明：如果是对双向链表做了多层索引扩展的特殊数据结构（比如跳表），可以实现接近O(log n)的查找效率，但这类结构已经不属于标准双向链表的范畴，不能和普通双向链表等价。

内容的提问来源于stack exchange，提问作者user14278552