使用二分查找的循环双向链表的复杂度是多少？
是 O(n log n) 还是 O(log n)？
Is it O(n log n) or O(log n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
是 O(n log n) 还是 O(log n)？
Is it O(n log n) or O(log n)?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
二分查找需要随机访问，因此在链表上是不可能的。您陷入了 O(n) 线性搜索。
Binary search requires random access, hence it's not possible on a linked list. You're stuck with an O(n) linear search.
我想说这不是 O(log n)，因为二分搜索在链表上效果不佳——你没有有效的随机访问。
如果您真的尝试进行二分搜索，则需要 O(log n) 步骤，但在每个步骤中，您需要 O(n) 遍历才能访问所需的元素。所以你可以说它是 O(nlog(n))。
您应该只进行 O(n) 线性搜索。
I'm going to say it's not O(log n) because binary searches don't work well on linked lists - you don't have efficient random access.
If you really tried to do binary search, it would take O(log n) steps, but in each step, you need an O(n) traversal to access the desired element. So you could say it's O(nlog(n)).
You should just do a O(n) linear search instead.