32二分检索(折半查找) 1.问题的描述 已知一个按非降次序排列的元素表a1 a23…an,判定某给定的元素x是否在该表中出 现。 >若是,则找出x在表中的位置并返回其所在下标 若非,则返回0值
3.2 二分检索（折半查找） 1. 问题的描述 已知一个按非降次序排列的元素表a1 , a2 , …,an ,判定某给定的元素x是否在该表中出 现。 ➢ 若是，则找出x在表中的位置并返回其所在下标 ➢ 若非，则返回0值
分治求解策略分析: 冷定义问题的形式描述:|=(n,a1,a2,…,an,x) 令问题分解:选取下标k,由此将分解为3个子问题: l1=(k-1 56123n=k-15 x) l2=(1,ak,x) 13=(n-k, ak+1, ak+2,,, an x) 对于2,若ak=x,则有解k,对1、l3不用再求解;否则, 若x<ak,则只在l1中求解,对不用求解; 若x>ak,则只在l3中求解,对1不用求解; 3上的求解可再次采用分治方法划分后求解 (递归过程) k的不同选择策略导致不同的检索算法:二分检 索, Fibonacci检索,线性插值检索,随机检索
分治求解策略分析： ❖ 定义问题的形式描述：I=(n, a1 , a2 , …,an ,x) ❖ 问题分解：选取下标k，由此将I分解为3个子问题： I1=(k-1, a1 , a2 , …,ak-1 ,x) I2=(1, ak ,x) I3=(n-k, ak+1, ak+2, …,an ,x) ➢ 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， ➢ 若x<ak，则只在I1中求解，对I3不用求解； ➢ 若x>ak，则只在I3中求解，对I1不用求解； I1 、I3上的求解可再次采用分治方法划分后求解 （递归过程） k的不同选择策略导致不同的检索算法：二分检 索，Fibonacci检索，线性插值检索，随机检索
2.二分检索算法 算法3.3二分检索 procedure BINSRCH(A, n,x,1) 注: integer low, high, mid,j, n; 给定一个按非降次 ow←1;high←n; while low≤ high do 序排列的元素数组 mid tl(low +high)/2 A(1:n),n≥1,判断x case 是否出现。 X≤A(mid)high←mid-1 x>A(midW←mid+1·若是,置j,使得 else: i←mid; return X=A(j) endcase repeat 若非,j=0 0 end nAsch
2. 二分检索算法 算法3.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 NIBSRCH(low + high)/2 注： 给定一个按非降次 序排列的元素数组 A(1:n)，n≥1,判断x 是否出现。 •若是，置j，使得 x=A(j) •若非，j=0
例31:设A(1:9)=(-15,-6,0,7,9,23,54,82,101) 在A中检索x=101,-14,82。执行轨迹见下表1 表1运行轨迹示例 x=101 14 X=82 low high mid low high mid low high mid 9 5 1689 9 521 999 578 9 8 8 9 921找不到 找到 找到 成功的检索 不成功的检索 成功的检索
例3.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 找不到 找到 找到 成功的检索 不成功的检索 成功的检索
3、算法的正确性证明 定理31过程 BINSRCH(An,x)能正确运行 证明: 1)在具体指定A中的数据元素及x的数据类型后,算法中的所有 运算都能按要求正确运行——即首先满足确定性和能行性 2)终止性 算法初始部分置low1,high←n ①若n=0,不进入循环,j置0,算法终止 ②否则,进入循环,计算mid, 或X=Amid),j置为mid,算法终止; 或κ<A(mi),置high←mid-1,搜索范围实际缩小为ow,md-1], 进入下次循环,对[mid+1,high]区间不做进一步搜索; 或x>A(mjd),置low←mid+1,进入下次循环;搜索范围实际缩小 为[mid+1,high],对[owmd们区间不做进一步搜索; 因low,high,mid都是整型变量,故按照上述规则,在有限步内,或找到 某个mid,有Amid)=x;或变得 Hlowhigh,在A中没有找到任何元素等于x, 算法终止
3. 算法的正确性证明 定理3.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， 算法终止