四大查找ASL的总结

一、一般线性表的顺序查找 ASL成功 = (n+1)/2 ASL失败 = （n+1)

二、有序线性表的顺序查找 ASL成功 = (n+1)/2 ASL失败 = n/(n+1) + n/2

三、二分查找 二分查找的ASL成功和ASL失败通过画出对应查找序列的判定树，进而进行计算。

四、索引查找 ASL = I块内 + I块间 其中块间可以使用二分查找。 （1）ASL = (b+1)/2 + (s+1)/2 块内和块间均使用顺序查找，由于n = s*b,可以通过构建方程，得到当s = n^(1/2)。 ASL最小为n^(1/2)+1 （2）ASL = (s+1)/2 + ceil(log2(b+1)) 块内顺序，块间二分