This earlier question讨论在O(n)时间内对双链接列表进行二进制搜索。该答案中的算法工作如下:
这对于双链接列表非常好,因为它可以向前和向后移动,但是这个算法不能在单链表中工作。
是否有可能使二进制搜索工作在时间O(n)上的单链表,而不是双链表?
发布于 2013-10-24 00:11:31
这是绝对有可能的,这是可行的。事实上,你只需要对双链接列表算法做一个改变就可以了。
单链接列表的问题是,如果您有指向列表中间的指针,则无法返回到列表的第一季度。然而,如果你想一想,你不需要从中间开始去做这件事。相反,你可以从清单的前面开始,走到第一季度。这需要(实质上)与以前相同的时间:与其后退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 )的总比较。唯一的区别是我们需要跟踪的额外指针。
希望这能有所帮助!
发布于 2013-10-24 00:22:06
比较需要O(1),更多的时间是遍历节点。因此,即使你持有指向n/2,n/4和3n/4的指针,找到它所需的时间仍然是O(n)。
此外,如果您从中间开始并返回(或向前),那么您最好沿途进行比较,因为进行另一次比较需要同样的时间: O(1)。
总结:
在链接列表上运行二进制搜索没有任何意义,除非链接列表由一个数组(ArrayList)备份,该数组允许直接访问O(1)中的元素。
发布于 2016-05-24 16:46:45
这可以通过使用双指针方法(只要列表按排序顺序)实现,如本研究工作中所述:http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
https://stackoverflow.com/questions/19554640
复制相似问题