对分查找复习公开课课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,对分查找算法,用一个数组,d(1)d(11),来存放,升序,的元素序列，,查找键,key,为,12,。,对分查找的过程,d(1),d(2),d(3),d(4),d(5),d(6),d(7),d(8),d(9),d(10),d(11),6,12,15,18,22,25,28,35,46,58,60,mid,第三次查找：,对分查找的过程,1,2,3,4,5,6,7,8,9,10,11,6,12,15,18,22,25,28,35,46,58,60,开始,i,j,mid,第一次查找：,第二次查找：,mid,j,j,i,mid,第四次查找：,流程图,未找到，输出结果：0,开始,i1，jn,i=j?,找到，输出结果：,m,结束,N,Y,计算中点,m(i+j)2,d(m)=key?,d(m)key?,im+1,jm-1,Y,Y,N,N,1.7,个学生的身高（单位,cm,）从高到低依次为：,178,177,175,172,170,165,162,。用对分查找找到,178,的过程中，依次被访问到的数据是,：（,）,A.178 B.172,175,178,C.172,177,178 D.172,175,177,178,练一练,若有,1024,个数据，,顺序查找最多查找次数为？,对,分查找,最多查找次数为？,对分查找的效率,i=1 j=1024,1.512,2.256,3.128,4.64,5.32,6.16,7.8,8.4,9.2,10.1,1.512,2.768,3.896,4.960,5.992,6.1008,7.1016,8.1024,9.1022,10.1023,11.1024,最多进行,log,2,n+1,次,练一练,2.,编写,VB,程序，实现如下功能：产生,10,个随机数升序排列在,list1,中，在,Text1,中输入一个正整数,key,单击,“,查找,”,按钮，用对分查找的思想在,label2,中显示查找结果。,对分查找复习,（,1,）前提：被查找的数据序列必须,有序,（,2,）基本思想：,在有序的数据序列中（一般放在数组中），首先把查找的数据与数组,中间位置,的元素进行比较，,若相等,，则查找成功并退出查找；,否则，根据数组元素的有序性,，确定数据应在数组的前半部分还是在后半部分查找；重复进行以上比较，直到找到或未找到为止。,（,3,）对,n,个有序数组对分查找的最多查找次数：,log,2,n+1,