找70 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 1921 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid
例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low 2 3 4 5 6 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 判定树： 6 3 9 4 10 2 8 D
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low 2 5 8 11 1 4 7 10 3 9 判定树： 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92
★算法评价 必判定树：描述查找过程的二叉树叫~ 有n个结点的判定树的深度为logn+1 折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 折半查找的ASL 设表长n=2-1,h=log2(n+1),即判定树是深度为h的满二叉树 设表中每个记录的查找概率相等，=】 则：4-2pe=2s=之2-”行gaa+-1bg,a+D-1 ni-
算法评价 ❖判定树：描述查找过程的二叉树叫~ ❖有n个结点的判定树的深度为log2n+1 ❖折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 ❖折半查找的ASL log ( 1) 1 log ( 1) 1 1 2 1 1 1 2 1, log ( 1), 2 2 1 1 1 1 2 + − + − + = = = = = = − = + = − = = n n n n j n c n ASL p c n p n h n h h j j n i i n i i i i h 则： 设表中每个记录的查找概率相等 设表长 即判定树是深度为 的满二叉树
§7.3分块查找 ★查找过程：将表分成几块，块内无序，块间有序； 先确定待查记录所在块，再在块内查找 ★适用条件：分块有序表 ★算法实现 用数组存放待查记录，每个数据元素至少含有关键字域 建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 ★算法描述 Ch7 3.txt Ch7_3.c
§7.3 分块查找 查找过程：将表分成几块，块内无序，块间有序； 先确定待查记录所在块，再在块内查找 适用条件：分块有序表 算法实现 ❖用数组存放待查记录,每个数据元素至少含有关键字域 ❖建立索引表，每个索引表结点含有最大关键字域和指 向本块第一个结点的指针 算法描述 Ch7_3.c