折半查找算法性能评价hn+>.2ASL =12(n+l)-1 ~ log2 n8nni=1分析：假设数据元素个数n恰好是满二又树时的结点个数，这样在二又树第i层上总共有2i-1个结点（设二又树的根结点所在层数为1），查找该层上的每个结点需要进行的比较次数等于该结点所在层的深度。练习1（多选题）使用折半查找算法时，要求被查文件：gB.记录的长度≤12A·采用链式存贴结构DV/记录按关键字递增有序C·采用顺序存贮结构
折半查找算法性能评价 n n n n i n ASL h i i 2 2 1 1 log ( 1) 1 log 1 2 1 + − + = = = − 练习1（多选题）使用折半查找算法时，要求被查文件： Ａ．采用链式存贮结构 Ｂ．记录的长度≤12 Ｃ．采用顺序存贮结构 Ｄ．记录按关键字递增有序 √ √ 分析：假设数据元素个数n恰好是满二叉树时的结点个数，这样 在二叉树第i层上总共有2 i-1个结点（设二叉树的根结点所在层数 为1），查找该层上的每个结点需要进行的比较次数等于该结点 所在层的深度
讨论：对顺序查找除了折半改进法外，还有无其他改进算法？有，例如分块查找法。9.2.3分块查找（索引）思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址。例：5874862448604920334244385322121389特点：块间有序，块内无序
9.2.3 分块查找（索引） 思路：先让数据分块有序，即分成若干子表，要求 每个子表中的数据元素值都比后一块中的数值小（但 子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中 还要包含每个子表的起始地址。 讨论：对顺序查找除了折半改进法外，还有无其他改进算法？ 有，例如分块查找法。 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 例： 特点：块间有序，块内无序