趣题：在双向有序链表中查找指定的数

大家都知道，在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没，在一个有序链表中又怎么样呢？让我们假设有这样一个链表，每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素（如果有的话）。另外，我们知道每个元素在内存中的地址，因此可以进行随机存取。或者可以说，这个有序链表中的所有元素都是储存在一个数组中的，但数组本身并不有序。

现在，我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来？

下面是一个平均复杂度为O(√n)的算法。在数组中随机选取Θ(√n)个数，然后通过不断地比较更新，找出这些数当中比x小的最大的数（不妨记作p），以及比x大的最小的数（记作q）。从p所在的位置出发，沿着链表往下走，直到找到x或者走到q（表明x不在链表中）为止。

可以证明，O(√n)已经是最优的了。