问题描述
这个较早的问题谈到在 O(n) 时间内对双向链表进行二分搜索.该答案中的算法如下:
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?
推荐答案
这绝对有可能实现.事实上，几乎只需对双向链表算法进行一项更改即可使其工作.
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.
希望这有帮助！
这篇关于如何在 O(n) 时间内对单向链表进行二分搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！