链表的搜索算法是否可能为O(logn(？根据我的理解，链表可以有O(n(或O(1(，因为你可以选择从哪里开始，从链表的开始到结束。知道了这一点，你能从中间开始寻找一个在O(logn(时间内运行的搜索算法吗？
只有以某种方式跳过读取元素，才有可能实现比O(n(遍历更快的遍历，除非你事先知道要跳过什么，并有额外的结构来跳到列表的各个部分，否则这是不可能的。如果你从开头或结尾开始，在找到你要找的东西之前，你必须平均搜索n/2个元素。如果你只有一个指针指向列表的中间，你仍然需要在每个方向上搜索n/2，这没有帮助。我们需要的是更多的结构，比如强加一个排序的标准。然后就可以实现这种"；跳过"；在O(n(空间中，并且通过实现O(logn("在O(log n(时间中搜索；跳过车道"；对于平均情况。这种数据结构被称为跳过列表，它保持快速的O(logn(插入。这些是与平衡树相同的渐近边界，但在概念上更接近链表。
需要O(logn(算法
- 在恒定时间内将列表划分为固定数量的部分，并且
- 确定搜索到的项目在恒定时间内位于哪个部分中
例如，对于跟踪其大小的排序索引数组数据结构的二进制搜索算法，可以直接根据数组的大小计算分割点，并且可以通过与分割点处的项目进行比较来确定搜索的项目是在前半部分还是后半部分。
但对于链表，你不知道它的大小，必须遍历它才能找到拆分点。这是一个O(n(运算，所以整体算法不能是O(logn(。
一般来说，第二个要求也没有得到满足。