二分查找过程可用二叉树来描述，我们把当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树，称为描述二分查找的判定树或比较树6
16 二分查找过程可用二叉树来描述，我们 把当前查找区间的中间位置上的记录作为根， 左子表和右子表中的记录分别作为根的左子 树和右子树，由此得到的二叉树，称为描述 二分查找的判定树或比较树
-8~10~80R/0.10I的二分查线的判定树(n=11)
17 R[0.10]的二分查线的判定树(n=11) 5 2 8 0 3 6 9 -∞～-1 1 2～3 4 5～6 7 8～9 10 0～1 1～2 3～4 4～5 6～7 7～8 9～10 10～∞ < > = < = > < = > < > = < > = < = > < = > < = > < = > < = > < = >
例9.1对于给定11个数据元素的有序表[2，310，15，20，25，28，29，30，35，40，采用2分查找，试问：(1)若查找给定值为20的元素，将依次与表中哪些元素比较？(2)若查找给定值为26的元素，将依次与哪些元素比较？(3）假设查找表中每个元素的概率相同，求查找成功时的平均查找长度和查找不成功时的平均查找长度18
18 例9.1对于给定11个数据元素的有序表{2，3， 10，15，20，25，28，29，30，35，40}，采用二 分查找，试问： (1)若查找给定值为20的元素，将依次与表中 哪些元素比较？ (2)若查找给定值为26的元素，将依次与哪些 元素比较？ (3)假设查找表中每个元素的概率相同，求查 找成功时的平均查找长度和查找不成功时的平均 查找长度
()若查1030找给定值为二分20的元素，查找依次与表中判定25 ,10 ,15树20元素比较共比较4次。40(2)若查找给定值为26的元素，依次与25，30，28元素比较共比较3次。(3)在查找成功时，会找到图中某个圆形结点，则成功时的1×1+2×2+4×3+4×4平均查找长度：ASLsucc=1在查找不成功时，会找到图中某个方形结点，则不成功时4×3+8×4的平均查找长度：ASLunsucc-3.6712
19 25 10 30 2 15 28 35 3 20 29 40 二分 查找 判定 树 (2)若查找给定值为26的元素，依次与25，30，28元素比较， 共比较3次。 (3)在查找成功时，会找到图中某个圆形结点，则成功时的 平均查找长度： 3 11 1 1 2 2 4 3 4 4 ASLsucc＝ ＝ + + + (1) 若 查 找给定值为 20的元素， 依次与表中 25，10，15， 20元素比较， 共比较4次。 在查找不成功时，会找到图中某个方形结点，则不成功时 的平均查找长度： 3.67 12 4 3 8 4 ASLunsucc ＝ ＝ +
9.2.3分块查找分块查找又称索引顺序查找，它是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将表R[0..n-1]均分为b块，前b-1块中记录个数为s=n/b]，最后一块即第b块的记录数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的；抽取各块中的最大关键字及其起始位置构成一个索引表IDX[0..b-1]，即IDX[i](0≤i<b-1)中存放着第i块的最大关键学及该块在表R中的起始位置。由于表R是分块有厚的所以索引表是一个递增有序表20
20 9.2.3 分块查找 分块查找又称索引顺序查找，它是一种性能介于顺 序查找和二分查找之间的查找方法。 它要求按如下的索引方式来存储线性表：将表 R[0.n-1]均分为b块，前b-1块中记录个数为s=n/b，最 后一块即第b块的记录数小于等于s；每一块中的关键字 不一定有序，但前一块中的最大关键字必须小于后一块 中的最小关键字，即要求表是“分块有序”的；抽取各 块 中 的 最 大 关 键 字 及 其 起 始 位 置 构 成 一 个 索 引 表 IDX[0.b-1]，即IDX[i](0≤i≤b-1)中存放着第i块的最大关 键字及该块在表R中的起始位置。由于表R是分块有序的， 所以索引表是一个递增有序表