实例分析(例2.1) 查找每个元素所需的元素比较次数统计如下: A (1)(2)(3)(4)(5)(6)(7)(8)(9 元素 15-6079235482101 成功检索比较次数 323(4 323(4 不成功检索比较次数3334433344 成功检索 最好:1次 最坏:4次 平均:(3+2+3+4+1+3+2+3+4)/9≈2.77次 ■不成功检索 最好:3次 最坏:4次 平均:(3+3+3+4+4+3+3+3+4+4)/10=34次
实例分析（例2.1） 查找每个元素所需的元素比较次数统计如下： A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼ 元素 -15 -6 0 7 9 23 54 82 101 成功检索比较次数 3 2 3 4 1 3 2 3 4 不成功检索比较次数 3 3 3 4 4 3 3 3 4 4 成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/9≈2.77次 ◼不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次
二元比较树 算法执行过程的主体是x与一系 列中间元素A(mid)比较。可用一棵二 元树描述这一过程,称为二元比较树 ■结点:分为内结点和外结点两种 >内结点:·代表一次元素比较 用圆形结点表示 存放一个m值(下标) ·代表成功检索情况 >外结点:·用方形结点表示, ·表示不成功检索情况 ■路径:代表检索中元素的比较序列 例2.1的二元比较树
二元比较树 算法执行过程的主体是x与一系 列中间元素A(mid)比较。可用一棵二 元树描述这一过程，称为二元比较树 ◼结点：分为内结点和外结点两种 ➢内结点：·代表一次元素比较 ·用 圆形结点表示 ·存放一个 mid值(下标) ·代表成功检索情况 ➢外结点：·用方形结点表示， ·表示不成功检索情况 ◼路径：代表检索中元素的比较序列 例2.1的二元比较树 5 2 7 1 3 6 8 4 9
二元比较树的查找过程 口若x在A中出现,则算法的执行过 程在一个圆形的内结点处结束 口若x不在A中出现,则算法的执行 过程在一个方形的外结点处结束 注:外结点不代表元素的比较,因0(8 为比较过程在该外结点的上 级的内结点处结束。 例21的二元比较树
二元比较树的查找过程 若x在A中出现，则算法的执行过 程在一个圆形的内结点处结束 若x不在A中出现，则算法的执行 过程在一个方形的外结点处结束 注：外结点不代表元素的比较，因 为比较过程在该外结点的上一 级的内结点处结束。 5 2 7 1 3 6 8 4 9 例2.1的二元比较树
定理22若n在区域[2k12)中,则对于,次成功的检索, BINSRCH至多做次比较;对于一次不成功的检索, 或者做k-1次比较,或者做k次比较。 证明要点: ≯二分检索中,每次mid取中值,故其二元比较树是一种“结点平衡”的树, ★当2k1≤n<2k时,结点分布情况为: 内结点:1至k级 外结点:k级或k+1级, ★外部结点在相邻的两级上—最深一层或倒数第2层 比较过程: 成功检索在内结点处结束,不成功检索在外结点处结束 成功检索在i级的某个内结点终止时,所需要的元素比较次数是i 不成功检索在j级的外部结点终止所需的元素比较次数是i-1
定理2.2 若n在区域[2k-1 ,2k )中，则对于一次成功的检索， BINSRCH至多做k次比较；对于一次不成功的检索， 或者做k-1次比较，或者做k次比较。 证明要点： ➢ 二分检索中，每次mid取中值，故其二元比较树是一种“结点平衡”的树， ★ 当2 k-1≤n<2 k时，结点分布情况为： 内结点：1至k级 外结点：k级或k+1级， ★ 外部结点在相邻的两级上——最深一层或倒数第2层 ➢比较过程： ► 成功检索在内结点处结束，不成功检索在外结点处结束 ► 成功检索在i级的某个内结点终止时，所需要的元素比较次数是i ► 不成功检索在i级的外部结点终止所需的元素比较次数是i-1
B| NSRCH的计算复杂度 n∈「2k1,2 k≈logn 1)外结点在最末的两级上,故不成功检索的最好 最坏和平均情况的计算时间均为⊙(logn) 2)最好情况下,成功检索的计算时间为⊙(1) 最坏情况下,成功检索的计算时间为⊙(logn)
BINSRCH的计算复杂度 n∈[2k-1 ,2k ) k≈logn 1）外结点在最末的两级上，故不成功检索的最好、 最坏和平均情况的计算时间均为 2）最好情况下，成功检索的计算时间为 最坏情况下，成功检索的计算时间为 Θ(logn) Θ(1) Θ(logn)