静态查找表 有序表的查找 折半查找(二分查找):先确定待查记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。 (条件:(1)表中数据的关键字有序 (2)表是顺序存储结构) (参见:P219)
静态查找表 ◼ 有序表的查找 折半查找（二分查找）：先确定待查记录所在的范围， 然后逐步缩小范围直到找到或找不到该记录为止。 （条件： （1）表中数据的关键字有序 （2）表是顺序存储结构 ） （参见：P219）
静态查找表 折半查找的算法 int Search Bin(SSTable St, Key Type key) i low=l; high-STlength; while(low<high i mid=(low+high)/2 if (eQ(key, STelem(mid].key)) return mid Ise if(t(key, STelem[mid]. key)) high=mid-1 else low=mid+1
静态查找表 ◼ 折半查找的算法 int Search_Bin(SSTable ST, KeyType key) { low=1; high=ST.length; while (low<high) { mid=(low+high)/2; if (EQ(key, ST.elem[mid].key)) return mid; else if(LT(key, ST.elem[mid].key)) high=mid-1; else low=mid+1; } }
静态查找表 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为log2n+1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过|og2n+1 成功平均查找长度: ASL=Σpc=1n2j.21=(n+1)n*og2(n+1)-1 (当n>50时) ASlbs=log2(n+1)-1
静态查找表 ◼ 折半查找的性能分析 (折半查找的过程可用二叉树来描述) 折半查找在查找成功时和给定值进行比较的关键字个数 至多为 log2n +1 折半查找在查找不成功时和给定值进行比较的关键字个 数最多也不超过 log2n +1 成功平均查找长度： ASLbs= ∑pici=1/n∑j.2j-1=(n+1)/n*log2 (n+1)-1 （当n>50时） ASLbs=log2 (n+1)-1
静态查找表 索引顺序表的查找(分块查找) (是顺序查找的一种改进。在此查找方法中,除表本身外,尚需 建立一个索引表。索引表按关键字有序。) 索引表 关键字项:其值为该子表内的最大关键字。 指针项:指示该子表的第一个记录在表中位置。 (参见:P225-图96) 分块查找过程 (1)先确定待查记录所在的块(子表),可采用顺序查找或折 半查找 (2)然后在块中顺序查找
静态查找表 ◼ 索引顺序表的查找（分块查找） （是顺序查找的一种改进。在此查找方法中，除表本身外，尚需 建立一个索引表。索引表按关键字有序。） ◼ 索引表 关键字项：其值为该子表内的最大关键字。 指针项：指示该子表的第一个记录在表中位置。 （参见：P225-图9.6） 分块查找过程： （1）先确定待查记录所在的块（子表），可采用顺序查找或折 半查找。 （2）然后在块中顺序查找
静态查找表 分块查找的算法即为折半查找或顺序查找的简单组合。 分块查找的平均查找长度为 aslbs=lb 其中:Lb:为査找索引表确定所在块的平均查找长度。 为在块中查找元素的平均查找长度。 若用顺序查找确定所在块,则 ASLb=(b+1)/2+(s+1)2=(n/s+s)/2+1 若用分块查找确定所在块,则 ASLbslog (n/s+1)+s/2 -般情况下:b=「ns
静态查找表 分块查找的算法即为折半查找或顺序查找的简单组合。 分块查找的平均查找长度为： ASLbs=Lb+Lw 其中： Lb：为查找索引表确定所在块的平均查找长度。 Lw：为在块中查找元素的平均查找长度。 若用顺序查找确定所在块，则： ASLbs=(b+1)/2+(s+1)/2=(n/s+s)/2+1 若用分块查找确定所在块，则： ASLbs≈log2 (n/s+1)+s/2 一般情况下：b= n/s s=√n