如何在排序链表上应用二分查找 O(log n)？
最近我在链表上发现了一个有趣的问题。给定了排序单链表，我们必须从该列表中搜索一个元素。
时间复杂度不应超过O(log n)。看来我们需要对这个链表应用二分查找。如何？由于链表不提供随机访问，如果我们尝试应用二分搜索算法，它将达到 O(n)，因为我们需要找到列表的长度并转到中间。
有什么想法吗？
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.
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.
Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
对于普通的单链表来说这当然是不可能的。
草图证明：要检查单链表的最后一个节点，我们必须执行跟随“下一个”指针的
n-1操作[通过归纳证明只有一个对第 k+1 个节点，并且它在第 k 个节点中，并且需要一个操作来跟随它]。对于某些输入，有必要检查最后一个节点（具体来说，搜索的元素是否等于或大于其值）。因此，对于某些输入，所需的时间与n成正比。您要么需要更多时间，要么需要不同的数据结构。
请注意，您可以使用二分搜索在 O(log n) 次比较中完成此操作。只是需要比这更多的时间，所以只有当比较比列表遍历昂贵得多时，这个事实才有意义。
It is certainly not possible with a plain singly-linked list.
Sketch proof: to examine the last node of a singly-linked list, we must perform
n-1operations of following a "next" pointer [proof by induction on the fact that there is only one reference to thek+1th node, and it is in thekth 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 ton.You either need more time, or a different data structure.
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.
您需要使用跳过列表。这对于普通链表来说是不可能的（我真的想知道这对于普通列表是否可行）。
You need to use skip list. This is not possible with a normal linked list (and I really want to learn if this is possible with normal list).
在链表中，二分查找可能无法实现 O(log n) 的复杂度，但至少可以通过使用双指针方法实现一点，如本研究工作中所述：http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
In Linked List, binary search may not achieve a complexity of O(log n) but least can be achieved a little by using Double Pointer Method as described here in this research work: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
如前所述，这通常是不可能的。然而，在像 C 这样的语言中，如果列表节点是连续分配的，则可以将该结构视为节点数组。
显然，这只是该问题的技巧问题变体的答案，但该问题始终是不可能的或技巧问题。
As noted, this is not in general possible. However, in a language like C, if the list nodes are contiguously allocated, it would be possible to treat the structure as an array of nodes.
Obviously, this is only an answer to a trick question variant of this problem, but the problem is always an impossibility or a trick question.
是的，在java语言中可以如下所示......
在任何
List上进行二分搜索。它适用于ArrayList和LinkedList以及任何其他List。Yes, it is possible in java language as below..
for binary search on any
List. It works onArrayListand onLinkedListand on any otherList.使用 MAPS 创建链接列表。
映射 M ，M[第一个元素]=第二个元素，M[第二个元素]=第三个元素，
...
...
它是一个链接列表...
但因为它是一张地图...
它内部使用二分搜索来搜索任何元素..
任何元素搜索都将花费 O(log n)
Use MAPS to create LINK LISTS.
Map M , M[first element]=second element , M[second element]=third element ,
...
...
its a linked list...
but because its a map...
which internally uses binary search to search any element..
any searching of elements will take O(log n)