18 42 49 折半查找过程的判定树 3
31 18 42 7 23 35 49 14 21 29 38 46 52 折半查找过程的判定树
5、性能分析： 查找成功时，走了一条从根结点到该记录结点的路径，比较 的次数正好是该记录结点所在的层数； ASL=PC=1a×2°+2x2+.+kx2-) i=l n+llog2(n+1)-1 = ≈log2(n+1)）-1 查找失败时也是走了一条从根结点到某一 终端结点的路径，比较次数等于lg2(n+1);
5、性能分析: 查找成功时,走了一条从根结点到该记录结点的路径,比较 的次数正好是该记录结点所在的层数; 查找失败时也是走了一条从根结点到某一 终端结点的路径,比较次数等于㏒2 (n+1) ； log (n 1) 1 log (n 1) 1 n n 1 1 2 2 2 ... k 2 ) n 1 ASL P C 2 2 0 1 k 1 i n i 1 i + − + − + = = = + + + − = （
三、分块查找 1、又称索引顺序查找，是顺序查找方法的又一改进方法： 2、基本思想：按照表内记录的某种属性把表分成n(n21) 个块（子表)，并建立一个相应的索引表 索引表的每个元素对应一个块，其中包括 该 块的起始位置和块内最大关键字值而且 按 其关键字有序排列
三、分块查找 1、又称索引顺序查找，是顺序查找方法的又一改进方法； 2、基本思想：按照表内记录的某种属性把表分成n (n≥1) 个块（子表），并建立一个相应的索引表 ， 索引表的每个元素对应一个块，其中包括 该 块的起始位置和块内最大关键字值，而且 按 其关键字有序排列
3、步骤： 第一步：在索引表中确定给定值k所在的块（可以是顺 序查找也可以是折半查找)： 第二步：在这个块中查找给定值（顺序查找）
3、步骤： 第一步：在索引表中确定给定值k所在的块（可以是顺 序查找也可以是折半查找）； 第二步： 在这个块中查找给定值（顺序查找）
索引表 33 66 99 各块内的最大关键字值 0 5 10 各块起始位置 1018 33 288 3850 60 6642 70 59 83 99 78 0 234567891011121314 若给定值k=50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 33 66 0 5 99 10 10 18 33 28 8 38 50 60 66 42 70 59 83 99 78 索引表 各块内的最大关键字值 各块起始位置 若给定值k=50