North China Electric Power University I P1:为查找表中第个元素的概率 C;1:为查到表中第个元素时已经进行的比较次数 在顺序查找时,C;取决于所查元素在表中的位置 i;=设每个元素的查找概率相等,即P=1,则 ASL=∑PcC1=(n+1)2 查找不成功的查找长度为n+1。 顺序查找表的优点:算法简单且适应面广,对表的结 构无任何要求,无论元素是否按关键字有序都可应用 顺序查找表的缺点:平均查找长度比较大,特别是当n 较大时,查找效率较低
North China Electric Power University Pi :为查找表中第i个元素的概率 Ci :为查到表中第i个元素时已经进行的比较次数 在顺序查找时，Ci取决于所查元素在表中的位置， Ci =i,设每个元素的查找概率相等，即Pi=1/n,则: ASL=∑PiCi=(n+1)/2 查找不成功的查找长度为n+1。 顺序查找表的优点：算法简单且适应面广，对表的结 构无任何要求，无论元素是否按关键字有序都可应用。 顺序查找表的缺点：平均查找长度比较大，特别是当n 较大时，查找效率较低
North China Electric Power University I 2)折半查找(有序表上进行查找): 基本思想:设三个指针ow,high和md分别指示待查有 序表的表头,表尾和中间元素,在开始查找时,三个 指针的初值分别为:low:=;hgh:=n;md:=(ow+high) div2。折半查找是从表的中间元素开始,用待查元素 的关键字k和 tImid. key比较,此时有三种情况(假设该 查找表按关键字的非递减次序排列): )若 tImid. key=k,则查找成功; 2)若 tImid key>k,则k必在较低标号的那一半表中, 令high:=mid-1 3)若 rmid. key<k,则k必在较高标号的那一半表中, 令low:=mid+1 再取中间项进行比较,直到查找成功或low>hgh查找 失败)为止
North China Electric Power University 2)折半查找(有序表上进行查找)： 基本思想：设三个指针low,high和mid分别指示待查有 序表的表头，表尾和中间元素，在开始查找时，三个 指针的初值分别为：low:=1;high:=n;mid:=(low+high) div 2 。折半查找是从表的中间元素开始，用待查元素 的关键字k和r[mid].key比较，此时有三种情况 (假设该 查找表按关键字的非递减次序排列) ： 1) 若r[mid].key=k，则查找成功； 2) 若r[mid].key>k，则k必在较低标号的那一半表中， 令 high:=mid-1 3) 若r[mid].key<k，则k必在较高标号的那一半表中， 令low:=mid+1 再取中间项进行比较，直到查找成功或low>high(查找 失败)为止
North China Electric Power University I 例:给出表元素关键字为:05,13,9,21,37567:8.892 1査找关键字k=21的情况 (I)low: =l; high: =ll; mid: =(1+lldiv 2=6 0513192137566475808892 lowl high 因为 rmid. key>k,所以向左找,令high:=md-1=5 (2 )low: =l;high: =5; mid: =(1+5)div 2=3 0513192137566475808892 mI hi 因为r| mid]. key<k,所以向右找,令low:=mid+1=4 (3)low:=4;high:=5;mid:=(4+5div2=4 0513192137566475808892 lowl I mid I high 因为 mid key==k,查找成功,所查元素在表中的序号为md的值
North China Electric Power University 例：给出表元素关键字为：{05,13,19,21,37,56,64,75,80,88,92} 1.查找关键字k=21 的情况 (1) low:=1;high:=11;mid:=(1+11) div 2=6 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key>k，所以向左找，令high:=mid-1=5 (2) low:=1;high:=5;mid:=(1+5) div 2=3 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key<k，所以向右找，令low:=mid+1=4 (3) low:=4;high:=5;mid:=(4+5) div 2=4 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key=k，查找成功，所查元素在表中的序号为mid 的值
North China Electric Power University I 2查找关键字k=85的情况 D)low:l; high: =ll; mid: =(1+11)div 2=6 0513192137566475808892 m high 因为r| mid key<k,所以向右找,令ow:=md+1-=7 (2 ) low: =7;high: =ll; mid: =(7+11)div 2=9 0513192137566475808892 lowl m d high 因为 rmid. key<k,所以向右找,令low:=mid+1=10 (3)low:=10;high:=ll;mid:=(10+11)div2=10 0513192137566475808892 lowl I mid I high 因为r| mid. key>k,所以向左找,high:=mid-1=9 因为ow>high,所以查找失败
North China Electric Power University (1) low:=1;high:=11;mid:=(1+11) div 2=6 因为r[mid].key<k，所以向右找，令low:=mid+1=7 (2) low:=7;high:=11;mid:=(7+11) div 2=9 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key<k，所以向右找，令low:=mid+1=10 (3) low:=10;high:=11;mid:=(10+11) div 2=10 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为r[mid].key>k，所以向左找，high:=mid-1=9 2.查找关键字k=85 的情况 05 13 19 21 37 56 64 75 80 88 92 low mid high 因为low>high，所以查找失败
North China Electric Power University I Procedure Bin Search(r: stAble; k: KeyType); Begin OW high: =n; while low<=high Do I mid: =(lowthigh) div 2; ase krlmid. key: low: =mid+1; krlmid. key: write(mid); Return; I k<rlmid key: high: =mid-1; End case: Write(Unsucc) End
North China Electric Power University Procedure BinSearch(r:sqTable;k:KeyType); Begin low:=1; high:=n; while low<=high Do [ mid:=(low+high) div 2; Case k>r[mid].key: low:=mid+1; k=r[mid].key: [Write(mid);Return;] k<r[mid].key: high:=mid-1; EndCase; ] Write(‘Unsucc’); End;