2.4 查找课件（21张幻灯片）

课件21张PPT。　猜价格：31———40玩一玩对分查找算法及程序实现（1）对分查找是效率很高的查找方法，但前提是被查找的数据必须是有序的。 （2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。 （3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 对分查找算法原理m=(i+j)2 m=Fix（（i+j）/2）m=Int（（i+j）/2）用数组d（1 to 10）存放升序的数字序列i表示查找范围第一个数组元素下标（起始位置） j表示查找范围最后一个数组元素下标（终止位置） m表示查找范围内中间位置数组元素的下标（中间位置）分解对分查找过程m=(i+j)2key=48第一次110522m=(i+j)2key=48第一次110522第二次610845m=(i+j)2key=48第一次110522第二次610845第三次910948总结规律每次d(m)与Key比较会确定下一次查找范围i的取值规律：j的取值规律：用对分查找算法查找数据（以升序数列为例）i=m+1j=m-1 完成导学案上查找17表格的填写m=(i+j)2key=17第一次110522第二次14215第三次34317m=(i+j)2key=20第一次110522第二次14215第三次34317第四次44418第五次54总结规律根据i，j的初值，计算出中间位置m，比较Key与d(m)，相等则输出，否则确定新i或新j，直到找到为止，这样重复操作可以采用什么结构？循环结构继续进行重复查找的条件？i<=jDo while i<=j loopN开始i?1,j?10d(m) j Then Label2.Caption = "找不到！"key=val(text1.text)i=1:j=10m=(i+j)2i=m+1j=m-1对分查找算法程序实现对分查找算法实施前提：有序数字序列 中点位置的计算：（i+j)2 新的查找范围的确定i=m+1或者j=m-1 查找结束的判定条件：找到数据或者i>j 数组中每个数据的查找次数：3 2 3 1 3 2 3 4 3 2 3 4 1 3 2 3 4对分查找算法的最多查找次数 由于对分查找过程中的每次比较都能使搜索范围减半，根据规律可以得出： [log2n]+1数组中每个数据的查找次数：1、前提：数据是有序的 2、结束条件：i>j 3、如果d(m)key j=m-1 4、n个数据最多查找次数：[log2n]+1 对分查找课堂总结：The End 块If语句的格式单一条件可以这样写 if <条件> then 语句块1 endif双条件这样写 if <条件> then 语句块1 else 语句块2 endif 多条件 if <条件> then 语句块1 elseif <条件> then 语句块2 elseif <条件> then 语句块3 (省略) else 语句块n endif返回 循环语句的格式Do while 条件表达式 语句块 Loop For 循环变量 = 初值 To 终值 Step 步长 语句块 Next 循环变量 For循环语句主要用于循环次数已知的情况下返回 ... ...