《对半查找算法》PPT课件.ppt

对半查找算法,意溪中学 张智2008年6月24日星期二高一（5）班,一、复习,顺序查找：当查找的对象排列没有规律时，可以用顺序查找方法，即从头开始一个一个地按照对象元素排列顺序往下找，直到全部元素都查找一遍；若查找的元素是单个，则找到为止，并非全部查找一遍。如：排列一：统计红楼梦第三回中“黛玉”出现的次数。排列二：（12，45，10，-8，89，-156，1，.）有限序列中查找 25。,二、对半查找算法,1、特点 对半查找的实质是在一个有限且有序的对象中，通过每次减缩一半查找范围而达到迅速确定目标的一个有效算法。即对一个已经排好序的数组，先看中间的元素是不是要求元素。如果是就找到了，不是看比要找的元素大还是小，大的话，上前一部分用同样的方法再找，小的话去后一部分用同样的方法再找。,2、算法描述（自然语言描述）,（1）令待查序列为M（2）另temp=在序列M中要寻找的元素（3）leftpostion=序列M左边第一个元素的位置，即为1（4）rightpostion=序列M右边最后一个元素的位置，即len（M）（5）midpostion=（leftpostion+rightpostion）/2 序列M中间元素的位置。（6）若temp=Mmidpostion，则输出元素已经找到，位置为midpostion，退出。否则到（7）（7）若temp Mmidpostion，则leftpostion=midpostion，到（5）步，否则到（8）步。（8）rightpostion=midpostion，到（5）步。,3、案例分析 即问题4-12,题目：方程 x 3sin x=0 在（/2，）之间有一 个根，试把它求出来，要求准确度为0.0001。分析：区间（/2，）虽然是一个连续的空间，但 其序列中的数是有序排列（从小到大），而且方程在区间（/2，）具有单调性。所以可以用对半查找算法在（/2，）中去寻找根。,4、编程求根过程,（1）启动VB6.0中文版（2）在下图VB 工作界面中，双击箭头所指的窗体。,（3）在下图箭头所指的位置，单击click,该方框中列举了对应对象的相应事件。,单击该方框可以选择不同的对象名称。本例的对象为FORM即窗体对象。,（4）在箭头所指位置输入求解该方程的根的程序代码,代码为:A=3.1414926/2 B=3.1415926 E=0.0001Do C=(A+B)/2 D=C 3*Sin(C)If D0 then B=C If D 0 then A=CLOOP Until D=0 Or Abs(A B)E Print“X=”;C,（5）代码输入以后，单击运行 启动（或者 F5键）验证程序是否正确。,解释执行程序,（6）若无错误，则在箭头所指窗体上单击即可得出答案。,为什么是单击呢？,哦！对象与事件！,5、小结,对半查找算法适用的条件代码中，中间位置的计算方法左右位置变量的表示技巧,6、作业,书124页（5）（6）,谢谢,