题13

题13

题目

Q:已知一个长度为 16 的顺序表, 其元素按关键字有序排列, 若采用折半查找算法查找一个不存在的元素, 则比较的次数至少是 ( ) ,至多是 ( ) .
A. 4
B. 5
C. 6
D. 7

分析

A:手动画出来这16个元素，然后手动模拟，我是这样的，但是感觉不是很科学，折半查找的二叉判定树很重要，这里我们理解一下：折半查找的判定树

解

A、B
对于此类题, 有两种做法: 一种方法是, 画出查找过程中构成的判定树, 让最小的分支高度对应于最少的比较次数, 让最大的分支高度对应于最多的比较次数, 出现类似于长度为 15 的顺序表时, 判定树刚好是一棵满树, 此时最多比较次数与最少比较次数相等;
另一种方法是, 直接用公式求出最小的分支高度和最大分支高度,从前面的讲解不难看出最大分支高度为 ,这对应的就是最多比较次数, 然后由于判定树不是一棵满树, 所以至少应该是 4 (由判定树的各分支高度最多相差 1 得出)。
注意, 若是求查找成功或查找失败的平均查找长度, 则需要画出判定树进行求解。
此外, 对长度为 的有序表,采用折半查找时,查找成功和查找失败的最多比较次数相同,均为 。