tem*_*def 16 algorithm big-o linked-list binary-search data-structures
这个早期的问题讨论了在O(n)时间内在双向链表上进行二进制搜索.该答案中的算法工作如下:
这对于双向链接列表非常有效,因为它可以向前和向后移动,但是这种算法在单链表中不起作用.
是否有可能在单链表而不是双链表上及时进行二进制搜索O(n)？
tem*_*def 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)总比较.唯一的区别是我们需要跟踪的额外指针.
希望这可以帮助!