《对分查找算法》一轮复习

1、德清一中 杨月霞对分查找算法复习前提：前提是被查找的数据必须是 的（递增/递减）意义：对分查找的高效性。试想：将全国13亿人按身份证号排列后，你可在31次比较 后找到这个人的信息。 若用顺序查找还有这个效率吗？有序Key = Val(Text1.Text)i = 1:j = n：p=0Do While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then Else End IfLoop 对分查找的核心代码：（以n个元素的递增数组为例） i=m+1j=m-1Dim a(1 to n) as integer,当n=1

2、0时数组元素排列如下：a(1)a(2)a(3)a(4)a(5)a(6)a(7)a(8)a(9)a(10)1347111619202730第一次a(1)1a(2)3a(3)4a(4)7a(5)11a(6)16a(7)19a(8)20a(9)27a(10)30第二次a(1)1a(2)3a(3)4a(4)7a(5)11m=5a(6)16a(7)19a(8)20a(9)27a(10)30第三次a(1)1a(2)3a(3)4a(4)7a(5)11m=5a(6)16i=6a(7)19a(8)20a(9)27a(10)30第四次非法区间a(2)3a(3)4a(4)7a(5)11m=5a(6)16i=6a(7

3、)19a(8)20a(9)27i=9m=9a(10)30key=26i=1j=10m=5i=6j=10m=8i=9m=9j=10j=8对分查找一般过程归纳（以n个元素的递增数组为例）：1、i的初值=1； j的初值=n2、中间数的下标m与i，j的关系是：m=Int(i+j)/2)3、确定退出循环的条件 区间的二个端点 i,j必须满足的条件是id(m)，说明应在下半区继续查找，修改i 还 是j? i=m+1 若keyd(m)，说明应在上半区继续查找，修改i 还 是j? j=m-1 1. (必做）数组变量d（1）到d（8）的值依次为87、76、69、66、56、45、37、23，用“对分查找”找到“

4、69”的过程中，依次被访问到的数据是（）A69B66、69C66、76、69D56、66、76、69热身训练2.（选做）在有序单词序列bike,cake,data,easy,feel, great,hive,mark, sweet中,用对分查找算法找到 easy过程中,依次被访问到的数据为feel, data. easygreat, data, easybike, cake, data, easy feel. cake. data, easy对分查找考点分析：（一）常规考点（二）数组元素下标值的变化规律（变量跟踪法）（三）搜索区间长度和查找次数（四）表达式的改变和查找成功后的处理方法对结果的影

5、响1. 某对分査找算法的VB程序段如下:i = 1: j = 9: n = 0key = Val(Textl.Text)Do While i = j n = n + 1 m = Fix(i + j) / 2) If key = d(m) Then Exit Do If key d(m) Then j = m - 1 Else i = m + 1Loop数组元素d(1)到d（9）的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是A.18或72 B. 12或61 C.39 D. 7或58（一）常规考点写出每一次循环结束后m,i,j,p

6、的值对分查找核心程序当Key=1时开 始：m=0,i=1,j=10,p=0第一次：第二次：第三次：Key = Val(Text1.Text)p=0:i = 1:j = nDo While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then i=m+1 Else j=m-1 End IfLoop 思考：循环结束时p=0意味着什么？当Key=20时开 始：m=0,i=1,j=10,p=0第一次：第二次：当Key=21时开 始：m=0,i=1,j=10,p=0第一次：第二次：第三次：a(1)a(2)a(3)a(4)a

7、(5)a(6)a(7)a(8)a(9)a(10)1347111619202730（二 ）数组元素下标值的变化规律（变量跟踪法）写出每一次循环结束后m,i,j,p的值对分查找核心程序当Key=1时开 始：m=0,i=1,j=10,p=0第一次：m=5,i=1,j=4,p=0第二次：m=2,i=1,j=2,p=0第三次：m=1,i=1,j=1,p=1Key = Val(Text1.Text)p=0:i = 1:j = nDo While i = j m=(i+j)2 If a(m) = Key Then p=m:Exit Do Else If a(m) Key Then i=m+1 Else j=

8、m-1 End IfLoop 当Key=20时开 始：m=0,i=1,j=10,p=0第一次：m=5,i=6,j=10,p=0第二次：m=8,i=6,j=10,p=8当Key=21时开 始：m=0,i=1,j=10,p=0第一次：m=5,i=6,j=10,p=0第二次：m=8,i=9,j=10,p=0第三次：m=9,i=9,j=8,p=01. (必做）某对分查找算法的VB程序段如下：i=1: j=6: n=0: f=Falsekey=val(Text1.Text)Do while i=j and f=False n=n+1 m=(i+j)2 If key=d(m) then f=True If

9、 keyd(m) then j=m-1 Else i=m+1Loop数组元素d(1)到d(6)的值依次为“13，18，25，30，35，59”。文本框Text1中输入33后运行该程序，运行结束后下列说法不正确的是（ ）变量f的值为False变量i的值为5C. 变量m的值为4D. 变量n的值为2（二）数组元素下标值的变化规律（变量跟踪法）2.（选做）已知一无序数组a（下标1到n），通过引入数组b（下标1到n），使得a(b(1)a(b(2) a(b(3)a(b(n)（示例如图所示），对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是A. m的值是Fix(1+n)/2),中点值是

10、 a(m)B. m的值是Fix(1+n)/2),中点值是 a(b(m)C. m的值是Fix(b(1)+b(n)/2),中点值是 a(m)D. m的值是Fix(b(1)+b(n)/2),中点值是 a(b(m)（二）数组元素下标值的变化规律（变量跟踪法）对分查找算法的最多查找次数： Log2N+1查找次数剩余搜索区间1N/22N/223N/23mN/2m（三）搜索区间长度和查找次数1. (必做）某公司的员工管理系统中有1200条员工记录（每条员工记录已按员工编号升序排序），现用对分查找法搜索一员工信息，开始搜索的记录范围为1200条，若第5次对分查找后还需继续搜索，则第6次搜索的记录范围内的记录数

11、为（）18 19 37 752.（选做）有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用对分查找查找一个元素，则最多需要（ ）次比较就能确定是否存在所查找的元素A.11 B.12 C.13 D.14（三）搜索区间长度和查找次数（四）表达式的改变和查找成功后的处理方法对结果的影响1. (必做）Randomizekey = Int (Rnd*100)i = 1: j = 7s = Do While i = j m = (i + j) 2 If key = a(m) Then s=s+M : Exit Do End IfIf key a(m) Then j = m 1: s=s

12、+“L Else i = m + 1: s=s+“RLoopText1.Text =s数组元素a(1)到a(7)的值依次为“25,36,39,42,47,66,78”，执行该程序段,文本框Text1中显示的内容是“RLR，则可以确定随机产生的Key值范围是（ ）A（25，36）B（47，66）C（66,78)D(78,100)（四）表达式的改变和查找成功后的处理方法对结果的影响2. （选做）已知数组元素a(1)到a(9)的值依次为19,28,37,46,55,64,73,82,91,若在 Text1中输入29,然后执行以下程序段Key= Val(Text1.Text)10Text2.Text=

13、“ “i=1: j=9: f=FalseDo While i Key Then i=m+1 Else j=m-1 End IfText2. Text= Str(m)+Text2. TextLoop则在执行该程序段后,Text2中示的内容是A.5 7 8B.55 37 28 C.82 73 55D.8 7 5 对分算法几个注意问题： （1）对分查找的前提：被查找数据必须是有序的。 （2）新的查找范围的确定：i=m+1 或 j=m-1 （3）数组元素下标值的变化规律 （4）表达式的改变和查找成功后的处理方法对结果的影响 （5）对分查找算法的最多查找次数： Log2n+1课堂小结 数组a 为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a 中查找数据Key 的程序。实现该功能的VB 程序段如下：i = 1: j = 10Key = Val(Text1.Text)Do While i j Then s = 没有找到！ Else s = 位置： + Str(m)Text2.Text = s上述程序中方框处可选语句为：i = m + 1j = m - 1If Key a(m) Then j = m - 1 Else i = m + 1则（1）、（2）、