ASL（关键字的平均比较次数）=∑Pi*Ci(i....n)
n:记录的个数，Pi:查找第i个记录的概率（通常认为pi=1/n），ci：找到第i个记录所需要的比较次数。
顺序查找
例：
int Search_Seq( SSTable ST , KeyType key )
{ //若成功返回其位置信息，否则返回0
ST.R[0].key =key;
for( i=ST.length; ST.R[ i ].key!=key; - - i );
//不用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++)
return i;
}
1) 查找成功时的平均查找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+ ... +n)/n =(n+1)/2。
2)查找不成功时的平均查找长度 ASLf =n+1。
对于顺序查找，查找概率相等时，ASL相同。 查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其ASL要比无序表ASL小。
折半查找：
如图，根据判定树求解，假设每个元素的查找概率相等，则查找成功时的asl=1/11（概率）*（1*1+2*2+4*3+4*4）。第一层的一个数比较成功时所需比较次数一次，第二层的两个数需要两次，依此类推。即查找成功时比较次数：为该结点在判定树上的层次数，不超过树的深度 d = 【 log2 n 】（向下取值） + 1， 查找不成功的过程就是走了一条从根结点到外部结点的路径d或d-1。
最近在学数据结构，很多地方不会，所以整理一下，当做个笔记，错误的地方请指正。