如何在排序的链表上应用二进制搜索O(log n)？

Question

最近我在链表上遇到了一个有趣的问题.给出了单独排序的列表,我们必须从该列表中搜索一个元素.

时间复杂度不应超过O(log n).这似乎我们需要在此链表上应用二进制搜索.怎么样？由于链接列表不提供随机访问,如果我们尝试应用二进制搜索算法,它将达到O(n),因为我们需要找到列表的长度并转到中间.

有任何想法吗？

Answer 1

用一个简单的单链表来肯定是不可能的.

草图证明:要检查单链表的最后一个节点,我们必须执行n-1跟随"下一个"指针的操作[通过归纳证明只有一个对k+1第th个节点的引用,并且它在k第节点,它需要一个操作来遵循它].对于某些输入,有必要检查最后一个节点(具体地说,如果搜索的元素等于或大于其值).因此,对于某些输入,所需的时间与...成比例n.

您需要更多时间或不同的数据结构.

请注意,您可以使用二进制搜索在O(log n)比较中执行此操作.它只需要花费更多的时间,所以如果比较比列表遍历要昂贵得多,那么这个事实才有意义.

Answer 2

您需要使用跳过列表.使用普通链表无法做到这一点(我真的想知道普通列表是否可行).