2.二分检索 分检索:每次选取中间元素的下标 算法2.3二分检索 procedure BINSRCH(A, n, x,j integer low, high, mid,j, n 注 oW←1;high←n 给定一个按非降次序排列 While low≤ high do 的元素数组A(1n),n≥1, mid←(ow+hgh2」 判断x是否出现。 case X≤A(md)high←mid-1 若是,置j,使得ⅹ=A(j) X>A(mid)lW←mid+1 若非,j=0 else j←mid; return endcase repeat -0 end binsrch
2. 二分检索 二分检索：每次选取中间元素的下标 算法2.3 二分检索 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :x<A(mid):high←mid-1 :x>A(mid):low ←mid+1 :else:j←mid;return endcase repeat j←0 end BINSRCH(low + high)/2 注： 给定一个按非降次序排列 的元素数组A(1:n)，n≥1, 判断x是否出现。 •若是，置j，使得x=A(j) •若非，j=0
例21:设A(1:9)=(-15,-6,0,7,9,23,54,82,101) 在A中检索x=101,-14,82。执行轨迹见下表1 表1运行轨迹示例 x=101 x=-14 low high mid low high d OW high 9 5 5 9 5 找不到 找到 找到 成功的检索 不成功的检索 成功的检索
例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1 表1 运行轨迹示例 x=101 x=-14 x=82 low high mid low high mid low high mid 1 9 5 1 9 5 1 9 5 6 9 7 1 4 2 6 9 7 8 9 8 1 1 1 8 9 8 9 9 9 2 1 找不到 找到 找到 成功的检索 不成功的检索 成功的检索
定理21过程B| NSRCH(A,n,xj)能正确运行 证明 1)在具体指定A中的数据元素及x的数据类型后,算法中的所有运算都 能按要求正确运行——即首先满足确定性和能行性 2)终止性 算法初始部分置low←1,high←n ①若η=0,不进入循环,j置0,算法终止 ②否则,进入循环,计算mid, 或X=A(mid),j置为mid,算法终止: 或≤A(mid),置high←mid-1,搜索范围实际缩小为[ow,md-1 进入下次循环,对[md+1,hgh区间不做进一步搜索; 〉或x>A(mid),置low←mid+1,进入下次循环;搜索范围实际缩小 为[mid+1,high],对[ow,md-区间不做进一步搜索; 因low,high,mid都是整型变量,故按照上述规则,在有限步内,或 找到某个md,有Amid)=x;或变得 lehigh,在A中没有找到任何元 素等于ⅹ,算法终」
定理2.1 过程BINSRCH(A,n,x,j)能正确运行 证明： 1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都 能按要求正确运行——即首先满足确定性和能行性 2）终止性 算法初始部分置low←1, high←n ① 若n=0，不进入循环，j置0，算法终止 ② 否则，进入循环，计算mid, ➢ 或 x=A(mid)，j置为mid，算法终止； ➢ 或x<A(mid)，置high←mid-1，搜索范围实际缩小为[low, mid-1]， 进入下次循环，对[mid+1, high]区间不做进一步搜索； ➢ 或x>A(mid)，置low←mid+1，进入下次循环；搜索范围实际缩小 为[mid+1, high]，对[low, mid-1]区间不做进一步搜索； 因low, high, mid都是整型变量，故按照上述规则，在有限步内，或 找到某个mid，有A(mid) = x；或变得low>high，在A中没有找到任何元 素等于x，算法终止
3.性能分析 1)空间特性 n+5个空间位置(A,xj,mid, low, higl O 2)时间特性 区分以下情况进行分析 成功检索:指所检索的x恰好在A中出现 由于A中共有n个元素,故成功检索恰好有n种可能的情况 不成功检索:指x不出现在A中。 根据取值,不成功检索共有n艹1种可能的情况(取值区间): x<A(1)或A(i)<x<A(i+1),1≤i<n-1或x>A(n) 成功/不成功检索的最好情况:执行步数最少,计算时间最短 成功/不成功检索的最坏情况:执行步数最多,计算时间最长 >成功/不成功检索的平均情况:一般情况下计算时间的平均值
3. 性能分析 1）空间特性 n+5个空间位置(A,x,j, mid,low,high)——О(n) 2) 时间特性 区分以下情况进行分析 ➢ 成功检索：指所检索的x恰好在A中出现。 由于A中共有n个元素，故成功检索恰好有n种可能的情况 ➢ 不成功检索：指x不出现在A中。 根据取值，不成功检索共有n+1种可能的情况（取值区间）： x<A(1) 或 A(i)<x<A(i+1),1≤i<n-1 或 x>A(n) ➢成功/不成功检索的最好情况：执行步数最少，计算时间最短 ➢成功/不成功检索的最坏情况：执行步数最多，计算时间最长 ➢成功/不成功检索的平均情况：一般情况下计算时间的平均值
实例分析(例2.1) 运算的频率计数 procedure BINSRCH(A, n, x,j) 1. While循环体外语句的频 integer low, high, mid,j, n 率计数为1 oW<1;high←n While|ow≤ high do 2.集中考虑 While循环中x与A mid←(ow+high)/2」 中元素的比较运算 case -其它运算的频率计数 ≤A(md)high←mid-1 与比较运算相同的数量级 X>A(md):loW←mid+1 else:i←mid; return endcase 3.case语句的分析:假定只 repeat 需一次比较就可确定case ←0 语句控制是三种情况的哪 end bINSRCH 种
实例分析（例2.1） 运算的频率计数 1. while循环体外语句的频 率计数为1 2. 集中考虑while循环中x与A 中元素的比较运算 ——其它运算的频率计数 与比较运算相同的数量级 3. case语句的分析：假定只 需一次比较就可确定case 语句控制是三种情况的哪 一种。 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :x<A(mid):high←mid-1 :x>A(mid):low ←mid+1 :else:j←mid;return endcase repeat j←0 end BINSRCH (low + high)/2