logo标签列表

如何在O(n)时间内对单链表进行二分查找？

algorithmdata-structureslinked-listbig-obinary-search
16

这个旧问题 讨论了如何在O(n)时间内对双向链表进行二分查找。该答案中的算法如下：

  • 前往列表的中间进行第一次比较。
  • 如果与我们要查找的元素相等，则完成。
  • 如果大于我们要查找的元素，则向后半程走到开头的一半并重复。
  • 如果小于我们要查找的元素，则向前半程走到开头的一半并重复。

这对于双向链表来说完全有效，因为可以向前和向后移动，但是这个算法在单向链表上不起作用。

是否可能使二分查找在单向链表上的时间复杂度为O(n)而不是双向链表？

1
我在那个上下文中读到了这段话，很明显回答问题的意思是：“如果你提出了一个问题，然后找到了解决方案，那么请自由地回答这个问题。”肯定没有像这样的情况：“如果你已经知道答案，就先创建一个问题，然后立即回答这个问题。” - libik
7
“@libik-”在“提问页面”上有一个明确的复选框，特别允许你同时提出和回答问题。我非常确定这是为像这样的情况而设计的，但我可能错了。 - templatetypedef
1
这有什么意义呢？线性搜索的时间复杂度是O(n)，所以如果你的二分搜索也是O(n)，那么它们的复杂度是相同的。 - Barmar
2
@Barmar 的优点是，正如在下面的评论中 templatetypedef 所提到的，在比较非常昂贵的情况下，比遍历列表要高效得多。 - Nir Alfasi
5
我很容易就能看出你是个好人，而且你的意图也是好的。请无视“背景噪音” ;) - Nir Alfasi
显示剩余3条评论
3个回答
26

这绝对是可行的。实际上，你只需要对双向链表算法做一个改变就可以让它工作。

单向链表的问题在于，如果你有一个指向列表中间的指针，那么你无法倒退回到列表的第一季。但是，如果你仔细想想，你并不需要从中间开始做。相反，你可以从列表的前面开始走路，直到到达第一季。这和之前花费的时间基本相同：你不需要倒退n/4步，而是可以从前面开始，向前走n/4步。

现在假设你已经完成了第一步，在位置n/4或3n/4处。在这种情况下，如果你需要回退到位置n/8或5n/8，你将遇到与之前相同的问题。如果你需要到达位置n/8，那么你可以再次从列表的前面开始，向前走n/8步。那么5n/8呢？这里的诀窍是 - 如果你仍然有指向n/2点的指针，那么你可以从那里开始，向前走n/8步，这将带你到正确的位置。

更普遍地说，不要只存储指向列表中间的指针，而要存储两个指针：一个在值可能出现的范围的前面，一个在该范围的中间。如果你需要前进到列表中的下一个位置，请将指向范围开头的指针更新为指向范围中点，然后将指向范围中点的指针向列表末尾的一半前进一半。如果你需要后退到列表中的上一个位置，请将指向范围中点的指针更新为指向范围开头的指针，然后向前走一半。

总的来说，这与双向链表的时间复杂度完全相同：我们先走n/2步，然后走n/4步，再走n/8步，以此类推，总计O（n）步。我们还只进行O（log n）次比较。唯一的区别是我们需要额外的指针来跟踪。

希望这能帮到您！

1
比较操作的时间复杂度是O(1)，花费更多时间的是遍历节点。因此，即使您持有指向n/2、n/4和3n/4的指针，查找所需的时间仍将保持为O(n)。
此外，如果您从中间开始向后（或向前）移动，您可能会比较一路上的元素，因为执行另一个比较需要相同的时间：O(1)。
总之： 在链表上运行二分查找没有意义，除非该链表由数组（ArrayList）支持，可以以O(1)的时间直接访问其元素。
5
如果比较操作代价高昂，那么使用二分查找而不是普通查找实际上会带来巨大的好处。虽然步骤数略微增加，但比较次数将呈指数级减少。如果比较操作要比在列表中前进花费更多时间，那么使用二分查找将具有巨大的优势。 - templatetypedef
2
这个回答如何回答问题？问题不是是否可能在小于O(n)的时间内完成，也不是它是否有意义。问题是是否以及如何在O(n)的时间复杂度内完成。 - sepp2k
2
计算哈希码不太可能比直接比较更有效（例如，在字符串上调用哈希码会迭代整个字符串，因此相等比较实际上可能更有效，因为它可以短路）。只有在比较之前已经计算了哈希码，哈希码才能节省您的时间。 - sepp2k
1
a) 这里没有答案。 b) 它没有用处。它只包含了每个人都已经知道的信息（加上你的个人意见）。 - sepp2k
1
@Dukeling a) 在注释中明确说明了 b) 在过去的15年中，我甚至没有遇到过一种情况，即比较如此昂贵，以至于在比较昂贵时，您不会将数据保存在链接列表中。 c) 即使我知道如何在单向链表上执行二进制搜索，我也不会更改我的答案-我认为警告人们“不要在家里尝试”并提供合理的解释是一个好主意。 - Nir Alfasi
显示剩余7条评论
-1
1
这个想法足以成为同行评审的研究论文，令人惊讶。 - jbapple
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接