定理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，算法终止