分析顺序查找的时间性能定义：查找算法的平均查找长度(Average Search Length)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值nZPC,ASL =i=1其中：n为表长，P,为查找表中第i个记录的概率，且P=1，C,为找到该记录时，曾和给定i1值比较过的关键字的个数
定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。 分析顺序查找的时间性能 = = n i ASL Pi Ci 1 1 1 = = n i Pi
对顺序表而言，C,=n-1i+PASL = nP, +(n-l)P2 + +2Pn-1n在等概率查找的情况下，P==n顺序表香查找的平均查找长度为：n+lZ(n-i+1) =ASLSS2ni=1
在等概率查找的情况下， 顺序表查找的平均查找长度为： 对顺序表而言，Ci = n-i+1 n Pi 1 = 2 1 1 1 1 + = − + = = n (n i ) n ASL n i s s ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
在不等概率查找的情况下，ASLss在Pn≥Pn-1≥≥P2≥Pi时取极小值若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上
若查找概率无法事先测定，则查找 过程采取的改进办法是，在每次查找之 后，将刚刚查找到的记录直接移至表尾 的位置上。 在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值
有序查找表二、上述顺序查找表的查找算法简单但平均查找长度较大，特别不适用于表长较大的查找表若以有序表表示静态查找表，则进行。“折半香找过程可以基于
上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用 于表长较大的查找表。 二、有序查找表 若以有序表表示静态查找表，则 查找过程可以基于“折半”进行
例如：key=64的查找过程如下：ST.lengthST.elem80758892192105|1337566428039145671011low highmidlow指示查找区间的下界high指示查找区间的上界mid = (low+high)/2
05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2