2、折半査找的性能分析 先看上述11个元素的表的具体例子。每一个的比较次数。 1234567891011 513192137566475808892 这个查找过程可用图81所示的三又③3 树来描述。树中每个结点表示表中 一个记录,结点中的值为该记录在④( 表中的位置,通常称这个描述查找 8 过程的二叉树为判定树。 ●从判定树上可见,查21的过程恰好是走了一条从根到结点 (4)的路径,和给定值进行比较的关键字个数为该路径上 的结点数或结点4在判定树上的层次数。 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 2、折半查找的性能分析 ⚫ 先看上述11个元素的表的具体例子。每一个的比较次数。 ⚫ 这个查找过程可用图8.1所示的二叉 树来描述。树中每个结点表示表中 一个记录，结点中的值为该记录在 表中的位置，通常称这个描述查找 过程的二叉树为判定树。 2 8 11 10 1 4 7 3 9 6 5 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 ⚫ 从判定树上可见，查21的过程恰好是走了一条从根到结点 （4）的路径，和给定值进行比较的关键字个数为该路径上 的结点数或结点4在判定树上的层次数
二分法查找在查找成功时进行比较的关键字个数最多不超过 树的深度,而具有n个结点的判定树的深度为 Lloga n+1。所 以折半查找法在查找成功时和给定值进行比较的关键字个数 至多为og2n+1 树中层数为1的结点有1个,层数为2的结点有2个,层数为h 的结点有2h1个。假设表中每个记录的查找概率P=,则查 找成功时折半查找的平均查找长度为: 则:ASL=∑P ∑ 2/-1n+ log2(n+1)-1 对于任意的n,当n较大(n>50时),可有下列近似结果: A SLhs =log2(n+1-l 可见,折半查找的效率比顺序查找高,但折半查找只适用于 有序表,且限于顺序存储结构。 北京邮电大学自动化学院
北京邮电大学自动化学院 12 log ( 1) 1 1 2 1 1 2 1 1 1 1 + − + = = = = = − = = n n n j n c n ASL p c h j j n i i n i 则： i i ASLbs = log 2 (n +1) −1 ⚫ 二分法查找在查找成功时进行比较的关键字个数最多不超过 树的深度，而具有n个结点的判定树的深度为log2n+1。所 以折半查找法在查找成功时和给定值进行比较的关键字个数 至多为log2n+1 n Pi 1 = ⚫ 对于任意的n，当n较大（n>50时），可有下列近似结果： ⚫ 可见，折半查找的效率比顺序查找高，但折半查找只适用于 有序表，且限于顺序存储结构。 ⚫ 树中层数为1的结点有1个，层数为2的结点有2个，层数为h 的结点有2 h-1个。假设表中每个记录的查找概率 ，则查 找成功时折半查找的平均查找长度为：
、索引顺序表的查找(分块查找) ●若以索引顺序表表示静态查找表,则 search函数可用分块 查找来实现。分块查找又称索引顺序查找,这是顺序查找的 种改进方法。在此查找法中,除表本身以外,尚需要建立 个“索引表”。例如:下图所示为一个表及其索引表,表 中含有18个记录,可分成三个子表(R1,R2,…,R6) (R,R3,…,R12)、(R 1314 6 索引表 224886 查38 89101112131415161718 2212138920334244382448605874578653 北京邮电大学自劫化学院 13
北京邮电大学自动化学院 13 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 三、索引顺序表的查找（分块查找） ⚫ 若以索引顺序表表示静态查找表，则search函数可用分块 查找来实现。分块查找又称索引顺序查找，这是顺序查找的 一种改进方法。在此查找法中，除表本身以外，尚需要建立 一个“索引表”。例如：下图所示为一个表及其索引表，表 中含有18个记录，可分成三个子表（R1，R2，…，R6）、 （R7，R8，…，R12）、（R13，R14，…，R18）
索引顺序表的查找(分块查找) 分块登我方法所谓“分块有序”指的是第2个子表中所有 记录的关键字均大于第1子表中的最大关键字,第3子表中 的所有关键字均大于第2字表中的最大关键字,依次类推, 分快查找过程需分两步进行。先确定待查记录所在的块 (子表),然后在块中顺序查找 分块查找的平均长度为: AsLbS=Lb+L ●其中L为查找索引表确定所在块的平均查找长度,L为在 块中查找元素的平均查找长度。 ASh=1+、I、 b+1s+1 +S)+1 此时的平均查找长度不仅和表长有关,而且和每一块中 的记录个数s有关。 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ( ) 1 2 1 2 1 2 1 1 1 1 1 = + + + + + = + = + = = = s s b s n i s j b ASL L L s i b j b s b w ⚫ 分块查找方法 所谓“分块有序”指的是第2个子表中所有 记录的关键字均大于第1子表中的最大关键字，第3子表中 的所有关键字均大于第2字表中的最大关键字，依次类推， 分快查找过程需分两步进行。先确定待查记录所在的块 （子表），然后在块中顺序查找。 ⚫ 此时的平均查找长度不仅和表长有关，而且和每一块中 的记录个数s有关。 ⚫ 分块查找的平均长度为：ASLbS=Lb+Lw ⚫ 其中Lb为查找索引表确定所在块的平均查找长度，Lw为在 块中查找元素的平均查找长度。 三、索引顺序表的查找（分块查找）
查找方法的比较 顺序查找 二分法查找分块查找 ASL 最大 最小 两者之间 表结构 有序表 有序表 分块有序表 无序表 存储结构顺序存储结构顺序存储结构顺序存储结构 线性链表 线性链表 北京邮电大学自动化学院
北京邮电大学自动化学院 15 顺序查找 二分法查找 分块查找 ASL 最大 最小 两者之间 表结构 有序表 无序表 有序表 分块有序表 存储结构 顺序存储结构 线性链表 顺序存储结构 顺序存储结构 线性链表 查找方法的比较