最近我在链表上遇到了一个有趣的问题。给定排序的单链表，我们必须从该列表中搜索一个元素。
时间复杂度不应超过O(log n)。看来我们需要对这个链表进行二分查找。如何？由于链表不提供随机访问，如果我们尝试应用二进制搜索算法，它将达到 O(n)，因为我们需要找到列表的长度并转到中间。
有什么想法吗？
最佳答案
用普通的单链表肯定是不可能的。
草图证明:要检查单链表的最后一个节点，我们必须执行跟随“下一个”指针的n-1操作[通过归纳证明只有一个引用到第k+1个节点，它在第k个节点中，并且它需要一个操作来跟随它]。对于某些输入，有必要检查最后一个节点(具体来说，搜索的元素是否等于或大于其值)。因此，对于某些输入，所需时间与 n 成正比。
您要么需要更多时间，要么需要不同的数据结构。
请注意，您可以使用二进制搜索在 O(log n) 比较 中完成此操作。它只需要比这更多的时间，所以只有在比较比列表遍历昂贵得多的情况下，这个事实才有意义。
关于algorithm - 如何在排序的链表上应用二进制搜索 O(log n)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5281053/