如何在已排序的链表上应用二分搜索 O(log n)? [英] how to apply binary search O(log n) on a sorted linked list?

问题描述

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

Recently I came across one interesting question on linked list. Sorted singly linked list is given and we have to search one element from this list.

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

Time complexity should not be more than O(log n). This seems that we need to apply binary search on this linked list. How? As linked list does not provide random access if we try to apply binary search algorithm it will reach O(n) as we need to find length of the list and go to the middle.

有什么想法吗?

推荐答案

使用纯单向链表当然不可能.

It is certainly not possible with a plain singly-linked list.

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

Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a "next" pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to n.

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

You either need more time, or a different data structure.

请注意，您可以使用二进制搜索在 O(log n) 比较 中完成.它只会花费更多的时间，所以这个事实只有在比较比列表遍历昂贵得多的情况下才有意义.

Note that you can do it in O(log n) comparisons with a binary search. It'll just take more time than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.

这篇关于如何在已排序的链表上应用二分搜索 O(log n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！