资源描述
单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,#,信息那些事儿,第七讲 那些查找,对分查找,信息那些事儿第七讲 那些查找对分查找,1,查找,基本思想,一,猜数游戏,查找基本思想一猜数游戏,2,1.,对分查找有哪些要求？,查找,基本思想,一,2.,对分查找的基本思想是什么？,被查找数据必须是,有序,首先将要查找的数据与待查找有序数组内处于中间位置的数据进行比较，如中间位置上的数与目标数据不同，根据有序性，就可确定应该继续在数组的前半部分还是后半部分查找。,在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。,1.对分查找有哪些要求？查找基本思想一2.对分查找的基,3,查找,基本思想,一,如何确定有序数组的“中间位置”？,我们用,i,代表查找范围的头，,j,代表查找范围的尾，,mid,代表中间位置，如何用,i,和,j,表示,mid,？,mid=(i+j)/2?,mid=(i+j)2 mid=Fix(i+j)/2)mid=Int(i+j)/2),查找基本思想一如何确定有序数组的“中间位置”？我们用i代表,4,查找,基本思想,一,请写出在数组,a(1)-a(7),：,1,22,33,44,55,66,77,中查找目标,key=55,过程中,i,j,mid,a(mid),的变化过程,i 1,j 7,mid 4,a(mid)44,5 5,7 5,6 5,66 55(,找到了,),查找基本思想一请写出在数组a(1)-a(7)：1,22,3,5,查找,基本思想,一,请写出在数组,a(1)-a(7),：,1,22,33,44,55,66,77,中查找目标,key=11,过程中,i,j,mid,a(mid),的变化过程,i 1,j 7,mid 4,a(mid)44,1 1 2,3 1 1,2 1,（头,尾？）,22 1,何时停下查找？,查找基本思想一请写出在数组a(1)-a(7)：1,22,3,6,查找,基本思想,一,Key,与,d(mid),的大小比较影响,i,j,的取值的规律：,i,的取值规律：,if d(mid)key then j=mid-1,用分支结构实现。,继续进行重复查找的条件：,ij,是结束查找。,查找基本思想一Key与d(mid)的大小比较影响i,j的取,7,查找,流程图,二,Y,Y,N,开始,i,1,j,10,计算,mid,d(mid)=key?,N,i,mid+1,j,mid-1,N,继续查找？,输出,“未找到”,Y,输出找到的信息,结束,d(mid)key?,Do while i=j,mid=(i+j)2,查找流程图二YYN开始i1,j10计算midd(mid),8,程序实现,三年,请结合流程图写出对分查找核心伪代码？,已知：被查找数据已经存储在数组,d,中并是有序的,程序实现三年请结合流程图写出对分查找核心伪代码？已知：被查,9,程序实现,三年,Do While i=j,mid=(i+j)2,If d(mid)=key Then,Text2.Text=,找到了，是第,&mid&,个,Exit Do,Else If d(mid)key Then,i=mid+1,Else,j=mid-1,End If,Loop,程序实现三年Do While i=j,10,对分查找的“中间位置”是如何确定？有哪些表示方式？,查找,对分查找的一些变形,四,mid=Int(i+j)/2+0.5)mid=(i+j+1)2 mid=Fix(i+j+1)/2)mid=Int(i+j+1)/2),mid=(i+j)2 mid=Fix(i+j)/2)mid=Int(i+j)/2),对分查找的“中间位置”是如何确定？有哪些表示方式？查找对分,11,对分查找的一些变形,四,Do While i=j And f=false,s=s+1,mid=(i+j)2,If d(mid)=key Then,Text2.Text=,找到了，是第,&mid&,个,f=True,Else If d(mid)key Then,i=mid+1,Else,j=mid-1,End If,Loop,对分查找的一些变形四Do While i=j And,12,对分查找的一些变形,四,Do While i=j And f=false,s=s+1,mid=(i+j)2,If d(mid)=key Then,Text2.Text=,找到了，是第,&mid&,个,f=True,End If,If d(mid)key Then,i=mid+1,Else,j=mid-1,End If,Loop,对分查找的一些变形四Do While i=j And,13,Thanks,信息那些事儿,Thanks信息那些事儿,14,
展开阅读全文