This earlier question讨论在 O(n) 时间内对双向链表进行二分查找。该答案中的算法工作如下:
- 转到列表中间进行第一次比较。
- 如果它等于我们正在寻找的元素，我们就完成了。
- 如果它比我们正在寻找的元素大，则向后走到开始的一半并重复。
- 如果它比我们正在寻找的元素小，则向前走到起点的一半并重复。
这对于双向链表非常有效，因为它可以向前和向后移动，但该算法不适用于单向链表。
是否可以在单链表而不是双向链表上使二进制搜索在时间 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) 总比较。唯一的区别是我们需要跟踪的额外指针。
希望这对您有所帮助!
关于algorithm - 如何在 O(n) 时间内对单链表进行二分查找？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19554640/