对分查找及程序实现富阳区新登中学施轶林【小游戏】从2,45,31,79,66,29,88,63,18,9,55中查找某一个数，该如何查找？【思考】还有其他更高效的方法吗？如果这组数有10万个，该怎么查找？【对分查找基本思想】首先将查找目标与有序数组内处于中间位置的元素进行比较，如果的值与目标相同，表示找到；否则根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找，直到获得最终结果。【tips】对分查找时，查找数据必须有序。顺序查找无此条件。位置1234567891011数据612151822252835465860【对分查找过程演示（key=35）】查找次数查找范围midkey与d(mid)的关系ijmid第一次d(1)-d(11)d(7)-d(11)第二次第三次第四次d(7)-d(8)d(8)6978key>d(mid)keyd(mid)key=d(mid)动画【小试身手】1.七名同学的身高（单位：cm）从高到低依次为：178,177,175,172,170,165,162，用对分查找找到178所需要的查找次数是次，依次访问到的数据是。2．有1000个数据按照从小到大的顺序存放在数组a(1to1000)中，使用顺序查找的最大次数为次，使用对分查找的最多次数为次。3172,177,178100010【结论】数据规模越大，对分查找效率越高；顺序查找最大查找次数：n次对分查找最大查找次数：Int(log2n+1)次输出m输出“未找到”NYi=1:j=n计算m的值key=d(m)？YNkeyjthenText2.Text="没有找到"m=(i+j)\2orj=m-1【对分查找程序实现】i=m+1【讨论】请说一说什么情况下，程序将终止查找？学案第3题【驾轻就熟】①Fori=1to100②ExitDo③Top=m-1学案第4题①Int((i+j)/2)②search=b(m):ExitFunction③a(m)
