9.1静态查找表 二.有序表的查找 有序表:查找表中记录按关键字有序排列的表 Bp: STelem(i] key<=STelem i+1] key i=1, 2,.. n-1 折半查找: 要求:查找表为有序表; 查找过程:先确定待查记录范围; 然后逐步缩小范围; 直到:查找成功或不成功
9.1 静态查找表 二. 有序表的查找 有序表 : 查找表中记录按关键字有序排列的表. 即: ST.elem[i].key<= ST.elem[i+1].key i=1,2,…,n-1 折半查找 : • 要求: 查找表为有序表; • 查找过程: 先确定待查记录范围; 然后逐步缩小范围; 直到: 查找成功或不成功
9.1静态查找表 折半査找算法: int Search Bin SSTable ST, Key Type key)( ∥在有序表ST中折半查找其关键字等于key的数据元素。若找到,则 函数值为该元素在表中的位置,否则为例:k=21,有序表为: low=1;high= STlength;∥/置区间初值 (5,13,19,2,37,56,64,75,80,88,92) while (low <=high)i mid=(low+ high)/2, 1. Low =l. high=ll. mid=6 if (eQ(key, STelem [mid]. key)) 2.°21<56high=6-1mid=3 return mid;∥找到待查元素 3.21>19low=4mid=4 else if (lt (key, ST elem[mid]. key)) 4. 21-=21 found-true return(4) high=mid-1;∥继续在前半区间进行查找 else low=md+1;∥/继续在后半区间进行查拉 折半查找的平均查找长度 return o;∥/顺序表中不存在待查元素 ASLbs=(n+1)/nlog2(n+1)-1 }∥ Search bin log2(n+1)-1
9.1 静态查找表 折半查找算法: int Search_Bin ( SSTable ST, KeyType key ) { // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则 //函数值为该元素在表中的位置，否则为0。 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; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 例: k=21, 有序表为: (5, 13, 19, 21, 37, 56, 64,75, 80, 88, 92) 1. Low =1, high=11, mid=6 2. ∵21<56 high=6-1 mid=3 3. ∵21>19 low=4 mid= 4 4. 21=21 found=true return(4) 折半查找的平均查找长度 ASLbs=(n+1)/nlog2(n+1)-1 ≈log2(n+1)-1
折半查找的平均查找长度分析 先看一个具体的情况,假设:n=11l 2+345H68910m C:34234134234 现构造一棵二叉树,将Ci=)结点放在这棵树的第层,Ci为比较次数 该二叉树可用以描述折半查找的过程,称之谓“折半查找的判定树” 例如:折半查找在m=11时的判定树如下: 0 8 二叉树描述的是整个折半查找的过程,对任何一个结点查找来说是走了一条 从根结点到该结点的一条路径,比较的次数正好是路径中的结点数目,也即结点 所在的层次。方块结点是查表不成功的区域。一般情况下,表长为n的折半查找 的判定树的深度和含有n个结点的完全二叉树的深度相同 对于上面的判定树平均查找次数,(1*1+2*2+4*3+4*4)/11
折半查找的平均查找长度分析 先看一个具体的情况，假设：n=11 现构造一棵二叉树，将Ci=i的结点放在这棵树的第i层，Ci为比较次数。 该二叉树可用以描述折半查找的过程，称之谓“折半查找的判定树” 例如: 折半查找在n=11 时的判定树如下： 二叉树描述的是整个折半查找的过程，对任何一个结点查找来说是走了一条 从根结点到该结点的一条路径，比较的次数正好是路径中的结点数目，也即结点 所在的层次。方块结点是查表不成功的区域。 一般情况下，表长为n的折半查找 的判定树的深度和含有n个结点的完全二叉树的深度相同。 对于上面的判定树平均查找次数，（1*1+2*2+4*3+4*4）/11 I 1 2 3 4 5 6 7 8 9 10 11 Ci 3 4 2 3 4 1 3 4 2 3 4
折半查找的平均查找长度分析 假设n=2-1并且查找概率相等则 ASL=∑C=∑×21 n+1og2(n+1)-1 n 在n>50时,可得近似结果 ASLb≈log2(n+1)-1
假设 n=2h -1 并且查找概率相等则 在n>50时，可得近似结果 折半查找的平均查找长度分析
9.1静态查找表 索引顺序表的查找(分块查找) 索引表: 1)按表中记录的关键字分块,R1,R2,RL 要求:第R块中的所有关键字<R+块中的所有关键字 k=1,2,,-1,称为“分块有序 2)对每块建立一个索引项,包含以两项内容: ①关键字项:为该块中最大关键字值; ②指针项:为该块第一个记录在表中位置. 3)所有索引项组成索引表
9.1 静态查找表 三. 索引顺序表的查找(分块查找) 索引表 : 1) 按表中记录的关键字分块, R1,R2,…,RL 要求: 第Rk 块中的所有关键字< Rk+1块中的所有关键字 k=1,2,…,L-1, 称为“分块有序” 2) 对每块建立一个索引项, 包含以两项内容: ① 关键字项: 为该块中最大关键字值; ② 指针项 : 为该块第一个记录在表中位置. 3) 所有索引项组成索引表