最近我在链表上遇到了一个有趣的问题。给出了排序的单链表，我们必须从这个列表中搜索一个元素。
时间复杂度不应超过O(log n). 这似乎我们需要在这个链表上应用二分查找。如何？由于链表不提供随机访问，如果我们尝试应用二进制搜索算法，它将达到 O(n)，因为我们需要找到链表的长度并走到中间。
有任何想法吗？
问问题
57108 次
6 回答
43
使用普通的单链表肯定是不可能的。
草图证明：要检查单链表的最后一个节点，我们必须执行以下n-1操作节点，并且它需要一个操作来跟随它]。对于某些输入，有必要检查最后一个节点（特别是，如果搜索到的元素等于或大于其值）。因此，对于某些输入，所需时间与 成正比。k+1kn
您要么需要更多时间，要么需要不同的数据结构。
请注意，您可以使用二进制搜索在 O(log n)比较中执行此操作。它只需要更多的时间，所以这个事实只有在比较比列表遍历更昂贵的情况下才有意义。
于 2011-03-12T09:45:45.357 回答
32
您需要使用跳过列表。这对于普通链表是不可能的（我真的很想知道这对于普通链表是否可行）。
于 2011-03-12T06:48:23.340 回答
2
在链表中，二分查找可能无法达到 O(log n) 的复杂度，但至少可以通过使用本研究工作中描述的双指针方法来实现一点点：http ://www.ijcsit.com/docs/Volume %205/vol5issue02/ijcsit20140502215.pdf
于 2016-05-24T16:50:24.073 回答
0
如前所述，这通常是不可能的。但是，在像 C 这样的语言中，如果列表节点是连续分配的，则可以将结构视为节点数组。
显然，这只是这个问题的一个技巧问题变体的答案，但问题总是一个不可能或一个技巧问题。
于 2013-09-10T13:45:03.353 回答
-1
是的，可以用java语言如下..
Collections.<T>binarySearch(List<T> list, T key)
对于任何List. 它适用ArrayList于LinkedList任何其他List.
于 2018-01-29T05:21:15.550 回答
-4
使用 MAPS 创建链接列表。
Map M , M[first element]=second element , M[second element]=third element ,
...
...
它是一个链表...
但是因为它是一个映射...
它在内部使用二进制搜索来搜索任何element..
任何元素的搜索都需要 O(log n)
于 2013-09-10T13:28:49.333 回答