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