这较早前的问题。在回答工作中的算法如下：

This earlier question talks about doing binary search over a doubly-linked list in O(n) time. The algorithm in that answer work as follows:

这工作得很好了的双的联的名单，因为它是可以移动向前和向后，但这种算法就不会在单链表的工作。

This works perfectly well for a doubly-linked list because it's possible to move both forwards and backwards, but this algorithm wouldn't work in a singly-linked list.

时有可能使在时间O（n）的二进制搜索工作在单链表，而不是一个双向链表？

Is it possible to make binary search work in time O(n) on a singly-linked list rather than a doubly-linked list?

推荐答案

这是绝对有可能使这项工作。事实上，有pretty的，你需要做的双向链表算法，使其运行得只有一个变化。

It's absolutely possible to make this work. In fact, there's pretty much only one change you need to make to the doubly-linked list algorithm to make it work.

与单链表的情况下的问题是，如果你有一个指针列表的中间，你不能倒退，回到列表的第一季度。但是，如果你仔细想想，你不需要从中间开始这样做。相反，你可以开始在列表的前的，然后步行到第一季度。这需要（基本上）相同的时间量前：而不是倒退N / 4个步骤，你就可以开始在前面走前锋N / 4步

The issue with the singly-linked list case is that if you have a pointer to the middle of the list, you can't go backwards to get back to the first quarter of the list. However, if you think about it, you don't need to start from the middle to do this. Instead, you can start at the front of the list and walk to the first quarter. This takes (essentially) the same amount of time as before: rather than going backward n / 4 steps, you can start at the front and go forwards n / 4 steps.

现在假设你已经做的第一步，是在位置N / 4或3N / 4。在这种情况下，你会像以前一样有同样的问题，如果你需要备份到位置n / 8或位置5N / 8。在这种情况下，你需要去N / 8的位置，你就可以开始在列表的前面再往前走几步N / 8个步骤。怎么样5N / 8的情况下？这里的窍门 - 如果你仍然有指向N / 2点，那么你就可以从那里开始并向前走N / 8个步骤，这将带你到正确的位置

Now suppose you've done the first step and are at position n / 4 or 3n / 4. In this case, you're going to have the same problem as before if you need to back up to position n / 8 or position 5n / 8. In the case that you need to get to position n / 8, you can start at the front of the list again and walk forward n / 8 steps. What about the 5n / 8 case? Here's the trick - if you still have pointer to the n / 2 point, then you can start there and walk forwards n / 8 steps, which will take you to the right spot.

更一般地，而不是存储一个指针列表的中间，商店的两个的指针到列表：一个是在范围的前部，其中的值可能是，一个在中间其中值可能的范围内。如果需要提前向前在列表中，更新指针范围的开始成为指针的范围的中间，然后步行指针在范围前进中途的范围的端部的中间。如果需要提前向后在列表中，更新指针在范围的中间成为指针的范围内的前部，然后往前行走中途

More generally, instead of storing a pointer to the middle of the list, store two pointers into the list: one at the front of the range where the value might be and one in the middle of the range where the value might be. If you need to advance forward in the list, update the pointer to the start of the range to be the pointer to the middle of the range, then walk the pointer to the middle of the range forward halfway to the end of the range. If you need to advance backward in the list, update the pointer to the middle of the range to be the pointer to the front of the range, then walk forwards halfway.

总的来说，这具有完全相同的时间复杂度的双向链接的情况下：我们取n / 2个步骤，则n / 4个步骤，则n / 8步骤等，这些总计为O（n）的总脚步。我们也只能使O（log n）的总的比较。唯一不同的是，我们需要跟踪的额外的指针。

Overall, this has the exact same time complexity as the doubly-linked case: we take n / 2 steps, then n / 4 steps, then n / 8 steps, etc., which sums up to O(n) total steps. We also only make O(log n) total comparisons. The only difference is the extra pointer we need to keep track of.

希望这有助于！