分顺序的时闻性能 定义:查找算法的平均查找长度 verage Search Length) 为确定记录在查找表中的位置,需和给定值进行比较的关键 字个数的期望值ASL=∑PC 其中:n为表长,P为查找表中第个记录的概率,且∑P=1 C为找到该记录时,曾和给定值比较过的关键字的个数 对顺序表而言,C=n1 ASL=nP,+(n-D)P2++2Pn+Pr 在等概率查找的情况下,P= 顺序表查找的平均查找长度为:ASL=∑mn-1+1) n+1 2 在不等概率查找情况下,ASL在P≥P产…≥P≥P1时取极小值 若查找概率无法事先测定,则查找过程采取的改进办法是在每次查 找之后将刚刚查找到的记录直接移至表尾的位置上
n i ASL PiCi 1 1 1 n i Pi 2 1 1 1 1 n (n i ) n ASL n i ss n Pi 1
讨论①查不到怎么办? 返回特殊标志,例如返回空记录或空指针。前例中设立了“哨兵”, 就是将关键字送入末地址ST.elem[0].key使之结束并返回i=0。 讨论②查找效率怎样计算?用平均查找长度ASL衡量。 讨论③如何计算ASL? 分析: 查找第1个元素所需的比较次数为1; 查找第2个元素所需的比较次数为2; 未考虑查找不成功的 e。。 情况:查找哨兵所需 查找第n个元素所需的比较次数为n; 的比较次数为n+1 总计全部比较次数为:1+2++m=(1+n)n/2 若求某一个元素的平均查找次数,还应当除以n(等概率), 即:ASL=(1+n)2时间效率为on) 讨论④顺序查找的特点: 这是查找成功的情况 优点:算法简单,且对顺序结构或链表结构均适用。 缺点:ASL太长,时间效率太低
有感找 问题:顺序查找表的查找算法简单,但平均查找长度较大,特别不适 用于表长较大的查找表。 办法:若以有序表表示静态查找表,则查找过程可以基于折半进行 查找过程:每次将待查记录所在区间缩小一半 °适用条件:采用顺序存储结构的有序表 算法实现 设表长为n,oW、high和md分别指向待查元素所在区间的上 界、下界和中点K为给定值 初始时,令0W=1,high=n,md(ow+high)2」 让k与md指向的记录比较 若k=rmd]key,查找成功 若k<rmid]key,则hgh≡md-1 若k>r[md]key,则low=md+1 重复上述操作,直至 ow>high时,查找失败
找21 1234567891011 51319213756475|8088|92 low mid high 234567891011 51319121371566475808892 low mid high 12345678910 5131921375664758088 92 lowmid high
234567891011 找70 513192137566475 5|80892 low mid high 12345 7891011 513192137566475808892 low mid high 34567891011 513192137566475|808892 low mid high 234567891011 192137 56 66475808892 low high mid 234567891011 513192137566475|808892 high low