logo标签列表

如何在已排序的链表中应用二分查找O(log n)？

algorithmdata-structureslinked-listcomplexity-theorybinary-search
42

最近我遇到了一个有趣的链表问题。给出一个按顺序排列的单向链表，我们需要在该链表中搜索一个元素。

时间复杂度不应超过O(log n)。这似乎需要我们在该链表上应用二分查找算法。如何操作呢？由于链表不提供随机访问，如果我们尝试应用二分查找算法，它将达到O(n)，因为我们需要找到链表的长度并前往中间位置。

有什么想法吗？

2
回避问题的答案是，如果您需要执行二分查找，则使用了错误的数据结构。 :) - drharris
5
这不是为什么发明跳表（skiplists）的原因吗？ - Jeffrey Greenham
如果有人仍然对此感兴趣，这里是我想出来的一个数据结构，可以完全实现这个功能：https://cs.stackexchange.com/questions/137076/does-this-data-structure-already-exist - Asad-ullah Khan
6个回答
45

使用普通的单向链表肯定是不可能实现的。

简要证明：要检查单向链表的最后一个节点，我们必须执行 n-1 次“下一个”指针操作 [归纳证明，因为第 k+1 个节点只有一个引用，并且是在第 k 个节点中，需要一次操作才能跟随它]。对于某些输入，必须检查最后一个节点（具体来说，如果搜索的元素等于或大于其值）。因此，对于某些输入，所需时间与 n 成比例。

你需要更多的时间或者不同的数据结构。

请注意，使用二分查找可以进行 O(log n) 比较，但需要更多的时间，因此仅在比遍历列表更昂贵的情况下，此事实才有意义。

33
你需要使用跳过列表。这在普通的链表中是不可能的（我真的想知道这是否在常规列表中可行）。
2
跳表是使用链表进行二分查找的解决方案。这是普通链表无法实现的。 - Zimbabao
3
应该接受这个回答。得票最高的答案要么误导要么不完整。它只是说“你可能需要其他东西”，这并不令人惊讶。而这个回答正中要害。 - BartoszKP
1
你不能使用跳表。这个问题涉及到单向链表。 - Marcin
6
这份回答清晰地解决了“单向链表”的问题。SkipList被提供作为一个合理的替代方案。 - BartoszKP
1
2
你链接中提供的论文中给出的方法甚至比线性搜索还要糟糕，因为查找中间指针会浪费很多时间。 - Xingjun Wang
0
正如所指出的，一般情况下是不可能的。但是，在像C这样的语言中，如果列表节点是连续分配的，那么可以将该结构视为一个节点数组。
显然，这只是对这个问题变种的一个技巧性回答，但问题总是不可能或者是一个技巧性问题。
这甚至不是一个技巧性的答案，因为如果你依赖于元素被连续存储，那么你就放弃了它作为链表的主要优势——O(1)的插入/删除时间。所以最好使用普通数组，而不必担心链表。 - BartoszKP
@BartoszKP 实际上不是这样的 - 这正是你不会失去的。这种结构的优点在于，在连续分配的区域中，您可以轻松地返回，但您也可以插入（导致非连续列表）。 - Marcin
@BartoszKP 不，跳表不是一个有效的答案，因为问题明确指定了单向链表。很抱歉你如此狭隘地关注你认为问题应该是什么，以至于无法回答实际提出的问题。 - Marcin
1
使用跳表的答案是最佳答案，原因如下： 1）它直接回答了问题，说明这在单向链表中是不可能的。 2）它提供了一个合理的替代方案，尽可能接近所提出的问题。我已经按照自己的判断对每个回答进行了踩票，不用担心。另外，我想知道最近谁给跳表答案点了踩 - 显然这不是一个明智的选择，而是嫉妒之情。 - BartoszKP
1
@BartoszKP 这个答案指出在一般情况下是不可能的。你只是喜欢跳表。至于“它提供了一个明智的替代方案，尽可能接近所提出的问题”，这很好，但这并不是一个理由来踩那些没有回答你希望被问到的问题的答案。 - Marcin
显示剩余5条评论
-1

是的，在Java语言中可以实现如下...

Collections.<T>binarySearch(List<T> list, T key)

用于任何List的二分查找。它适用于ArrayList、LinkedList和任何其他List。

在集合的上下文中，“List”有非常不同的含义，请参考官方文档。 - raviraja
-4
使用 MAPS 创建 LINK LISTS。
Map M，M [第一个元素] = 第二个元素，M [第二个元素] = 第三个元素，
...
...
它是一个链接列表...
但因为它是一个 map...
它内部使用二进制搜索来搜索任何元素...
任何元素的搜索都将花费 O(log n)。
1
显然这是一个骗局，没有人在意这里的问题和答案...这个答案有什么问题吗？能解释一下吗，Marcin？ - Monotosh Mondal
你需要更多时间或者一个不同的数据结构（Steve Jessop）。 - Monotosh Mondal
我给这个点了踩，因为它难以理解，而且就我所能理解的来看，它并没有回答问题。 - Marcin
难以理解...如何...它肯定回答了问题...使用log n搜索时间构建的链表...再次...不同的数据结构（Steve Jessop）...类似于这个，你可以在Perl中的关联数组中找到链表是如何构建的。 - Monotosh Mondal
(a) 过度使用省略号和垂直空间 (b) 您没有完全描述数据结构，但听起来它是所需的单向链表。 - Marcin
不回答问题，因为问题说明已从算法外部提供了排序的链表--您无法控制它。虽然引入新的数据结构可能是合理的，但构建该数据结构的成本必须包含在解决方案的成本中。也就是说，您已经获得了排序的链表。您的解决方案将创建一个基于该链表的映射并搜索该映射。创建地图的时间复杂度最好为O(n lg n)，搜索的时间复杂度为O(lg n)。因此，该解决方案的时间复杂度为O(n lg n + lg n)，即O(n lg n)。 - JaMiT
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接