大家都知道，在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没，在一个有序链表中又怎么样呢？让我们假设有这样一个链表，每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素（如果有的话）。另外，我们知道每个元素在内存中的地址，因此可以进行随机存取。或者可以说，这个有序链表中的所有元素都是储存在一个数组中的，但数组本身并不有序。
现在，我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来？
下面是一个平均复杂度为O(√n)的算法。在数组中随机选取Θ(√n)个数，然后通过不断地比较更新，找出这些数当中比x小的最大的数（不妨记作p），以及比x大的最小的数（记作q）。从p所在的位置出发，沿着链表往下走，直到找到x或者走到q（表明x不在链表中）为止。
可以证明，O(√n)已经是最优的了。
又是沙发?
终于到板凳了！
这算是有特定结构的双向有序链表？而且取随机数的时间复杂度呢？
跑一下题，在这里贴一个老外的中文blog的日志地址：
http://www.sinosplice.com/chinese/archives/2005/03/01/%E7%AC%AC%E4%B8%89%E5%A3%B0%EF%BC%9A%E4%B8%A4%E4%B8%AA%E9%97%AE%E9%A2%98/
应用语言学问题
不错哦. 可以用在静态链表.
为什么要是√n呢？
块链么?
回答地基
设取a个数，那么取数和比较的时间复杂度都是O(a)。最后再由那个数出发找到插入位置的复杂度是O(n/a)。
总复杂度是O(a+n/a)。易知要使复杂度最小,a要是√n级别的。
取随机数耗费比较大，具体实现时这个这个a应该比√n要小。具体大小。有待于做实验。
想到前年我用链表插入排序挂掉了了NOIp2007第一题。不过用这种方法似乎也没有办法通过。√10000=100,乘以200000，千万级要在1秒内出解似乎也是困难……
正在学习中~~
请问证明细节能写一下吗？如果随机找到的p和q都比x大，或者都比x小呢？继续随机找吗？多谢指点！
TO 10楼：
加上a[1]和a[n]不就行了？
如果取出来的数都比x小，或者都比x大呢？
哎，看来果然不存在查找时间复杂度为O(logn)而插入时间复杂度为O(1)的数据结构。
假如存在的话，基于比较的排序算法就可以轻松地将时间复杂度降至理论下限。
没要求空间的话 把整个链表映射到一个指针数组也可以实现logn的复杂度吧
CLRS Problem 10-3
正在学习中~~
写得太精彩了，以这样的篇幅写了这么大跨度的文章，精品。向楼主学习！