@算法82 e int Search_Bin( SSTable st,KeyType kval) ∥在有序表ST中折半查找其关键字等于kwa的数据元素。若找到,则函 ∥数值为该元素在表中的位置,否则为0 low=l; high=STength; ∥置区间初值 while (low < high)( 数据结 mid=(low high)/2; if (kval=STelem(mid key return mid;∥找到待查元素 else (kval <STelem(mid key high=mid-1;∥继续在前半区间内进行查找 low=mid+1;∥继续在后半区间内进行查找 3//while return 0 ∥顺序表中不存在待查元素 }∥ Search Bin 计算机教研宦 第16页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第16页 算法 8.2 int Search_Bin ( SSTable ST, KeyType kval ) { // 在有序表ST中折半查找其关键字等于kval的数据元素。若找到，则函 // 数值 为该元素在表中的位置，否则为0。 low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if （kval == ST.elem[mid].key ) return mid; // 找到待查元素 else if ( kval < ST.elem[mid].key ) high = mid - 1; // 继续在前半区间内进行查找 else low = mid + 1; // 继续在后半区间内进行查找 } //while return 0; // 顺序表中不存在待查元素 } // Search_Bin
分析折半查找的平均查找长度 先看一个具体的情况,假设:n=11 234567891011 Ci34234134234 判定树 6 3 9 7 10 8
先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 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
g·一般情况下,表长为n的折半查找的判定树的 深度和含有n个结点的完全二叉树的深度相同 假设n2h-1并且查找概率相等 数据结 则 AS=C=m∑ ×21/n+1 log2(n+1)-1 在n>50时,可得近似结果 AS bs g2(n+1)-1 计算机教研室 第18页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第18页 • 一般情况下，表长为 n 的折半查找的判定树的 深度和含有 n 个结点的完全二叉树的深度相同。 假设 n=2h -1 并且查找概率相等 则 在n>50时，可得近似结果 log ( 1) 1 1 2 1 1 2 1 1 1 + − + = = = = − = n n n j n C n ASL h j j n i b s i ASLbs log 2 (n +1) −1
@8.1.3分块查找 查找过程:将表分成几块,块内无序,块间有序;先确定待查记录 所在块,再在块内查找 适用条件:分块有序表 算法实现 用数组存放待查记录,每个数据元素至少含有关键字域 数据结 建立索引表,每个索引表结点含有最大关键字域和指向本块第1 个结点的指针 索表 224886 查38 4561789101l12131415161718 2212138920334244382448605874578653 计算机教研室产 第19页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第19页 8.1.3 分块查找 • 查找过程：将表分成几块，块内无序，块间有序；先确定待查记录 所在块，再在块内查找 • 适用条件：分块有序表 • 算法实现 – 用数组存放待查记录,每个数据元素至少含有关键字域 – 建立索引表，每个索引表结点含有最大关键字域和指向本块第1 个结点的指针 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查38