5.4查找算法的程序实现

1、,旧知回顾-对分查找,条件,被查找数据必须有序。,基本思想,首先将查找目标与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素值与查找目标相同，表示找到； 否则根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找，直到获得最终结果。,旧知回顾-对分查找,1. 八名同学的成绩从低到高依次为： 35,43,51, 60,72,77,86,90， 用对分查找找到72依次访问到的数据是 。,60,77,72,热身活动现场演示,对分查找,算法与程序设计,程序实现,周 玲 信息技术 杭州市富阳区新登中学,1 流程图-升序为例,i=j？,jm-1,im+1,m(i+j)2,【小

2、组合作】 补充完整流程图,2 程序实现,Key = Val(Text1.Text) i = 1 j = n Do While 计算出中间位置 If d(m) = Key Then Text2.Text = “在数组的”+ Str(m) +“号位置” Exit Do 查找成功立即终止循环 End If If d(m) j then Text2.Text = 没有找到,m=(i+j)2,i=m+1,j=m-1,i=j,3 小试身手,1. 在已排序的数组D中查找键值为Key的数，其对分查找的VB程序如下，请补充完整程序：,i=1 :j=n b=0 DO while ？ m=fix(i+j)/2) I

3、f d(m)=key then ？：exit do End If If key0 then text1.text=str(b) else text1.text=“没有找到”,i=j,j=m-1,b=m,3 小试身手,i=1:j=n xb=0 Do While id(m) B. keyd(m) D. key=d(m),A,2. 在已排序的数组d(数组元素d(1) d(2) d(n) )中查找键值为key的数，其对方查找的VB程序段如下：,4 提高练习,1.【加试题】某对分查找算法的VB程序段如下： i=1 ： j=9 : n=0 Key=Val(Text1.Text) Do While i =j

4、 n=n+1 m=Fix(i+j)/2) If key=d(m) Then Exit Do If keyd(m) Then j=m-1 Else i=m+1 Loop 数组元素d(1)到d(9)的值依次为”7,12,18,25,39,58,61,72,86”。 若该程序段运行结束后，n的值为2，则key的值是（ ） A. 39 B. 18或61 C. 18或72 D.12或61,D,4 练一练,C,2.【加试题】数组元素啊a(1)到a(8)的值依次为“4,21,37,54,68,73,77,96”，利用如下对分查找的算法查找数据“75”，该代码执行后m , i, j 三个变量的值分别是（ ） i=1: j=8: x=75 Do While ix Then j=m-1 Else i=m+1 Loop A. m=6 i=6 j=6 B. m=7 i=6 j=7 C. m=