16

这个较早的问题讨论了在 O(n) 时间内对双向链表进行二进制搜索。该答案中的算法如下工作：

  • 转到列表中间进行第一次比较。
  • 如果它等于我们正在寻找的元素，我们就完成了。
  • 如果它比我们正在寻找的元素大，则向后走到开始的一半并重复。
  • 如果它比我们正在寻找的元素小，则向前走到开始的一半并重复。

这对于双向链表非常有效，因为它可以向前和向后移动，但是这种算法在单向链表中不起作用。

是否可以在单链表而不是双链表上使二进制搜索在时间 O(n) 上工作？

4

3 回答 3

25

完全有可能完成这项工作。事实上，您几乎只需要对双向链表算法进行一项更改即可使其正常工作。

单链表案例的问题在于，如果您有一个指向列表中间的指针，您就不能向后返回到列表的第一季度。但是，如果您考虑一下，您不需要从中间开始执行此操作。相反，您可以从列表的前面开始，然后走到第一季度。这需要（基本上）与以前相同的时间：您可以从前面开始向前走 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) 的总比较。唯一的区别是我们需要跟踪的额外指针。

希望这可以帮助！

于 2013-10-24T00:11:31.120 回答
1

比较需要 O(1)，需要更多时间的是遍历节点。因此，即使您持有指向 n/2、n/4 和 3n/4 的指针，您找到它的时间仍然是 O(n)。

此外，如果您从中间开始并返回（或向前），您不妨沿途进行比较，因为进行另一次比较需要相同的时间：O(1)。

总结一下：
在链表上运行二进制搜索是没有意义的，除非链表由一个允许在 O(1) 中直接访问其元素的数组 (ArrayList) 支持。

于 2013-10-24T00:22:06.607 回答
-1

这可以通过使用双指针方法（如果列表按排序顺序）来实现，如本研究工作中所述：http ://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf

于 2016-05-24T16:46:45.240 回答