如何在O（n）时间内对单链接列表进行二进制搜索？

绝对有可能做到这一点。实际上，您只需对双链表算法进行一项更改即可使其工作。

单链接列表情况的问题是，如果您有一个指向列表中间的指针，则不能后退以返回列表的第一部分。但是，如果您考虑一下，则无需从中间开始。相反，你可以在启动 前
列表，然后步行到第一季度。这（基本上）花费与以前相同的时间：您可以从最前面开始向前前进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）总比较。唯一的区别是我们需要跟踪额外的指针。

希望这可以帮助！