最近我碰到一个有趣的问题来了链表。排序单链表，并给出我们必须从这个列表中搜索一个元素。

Recently I came across one interesting question on linked list. Sorted singly linked list is given and we have to search one element from this list.

时间复杂度应不超过 O（log n）的。这似乎是我们需要申请二进制搜索这个链表。怎么样？由于链表不提供随机访问，如果我们尝试运用二进制搜索算法将达到O（N），因为我们需要找到该列表的长度，然后转到中间位置。

Time complexity should not be more than O(log n). This seems that we need to apply binary search on this linked list. How? As linked list does not provide random access if we try to apply binary search algorithm it will reach O(n) as we need to find length of the list and go to the middle.

任何想法？

推荐答案

这当然是不可能的普通单链表。

It is certainly not possible with a plain singly-linked list.

素描证明：下面的下一个指针[证明用归纳法来考察的单链表的最后一个节点，我们必须执行 N-1 操作事实上，只有一个参照 K + 1 个节点，它是在 K 个节点，它需要一个操作遵循它。对于某些输入，有必要检查的最后一个节点（具体地，如果搜索的元素是等于或大于它的值）。因此，对于某些输入，所需的时间是成正比的 N 。

Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a "next" pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to n.

您要么需要更多的时间，或不同的数据结构。

You either need more time, or a different data structure.

请注意，你可以做它在O（log n）的比较的一个二进制搜索。这将只是把更多的时间的比，所以这其实只是感兴趣，如果比较是非常比列表遍历更加昂贵。

Note that you can do it in O(log n) comparisons with a binary search. It'll just take more time than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.