Ami*_*mar 2 c linked-list binary-search
我读过一个问题,是否可以在链接列表中应用二进制搜索？
由于链接列表不允许随机访问,因此这看起来几乎是不可能的.
任何人都有办法吗？
除了您没有对链表元素的固定时间访问之外,主要问题是您没有关于列表长度的信息.在这种情况下,你根本无法将列表"切割"成两半.
如果您对链表长度至少有一个限制,那么问题在O(log n)中是可解决的,确实是跳过列表方法.否则什么都不会让你无法阅读整个列表,因此O(n).
因此,假设链表已排序,并且您知道其长度(或至少是最大长度),是的,可以在链表上实现某种二进制搜索.但事实并非如此.