双向链表的二分搜索

html5 • • 问答

可以在 ?(log ) 时间内对双向链表执行二分查找吗？

我的答案是肯定的，因为如果列表已经有点排序，它可能比 O(n) 更快。

回答

为了对双向链表进行二分搜索，您必须首先迭代到列表的中间点，以便您可以对列表的两半进行第一次递归。

迭代到链表的中间点已经是一个 O(n) 操作，因为迭代到中间点所需的时间将随着链表本身变长而线性增长。

因此，您已经处于 O(n) 时间，甚至在您进行任何实际搜索之前。因此，答案是否定的。

以上是双向链表的二分搜索的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>