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