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)i?m+1继续查找？输出“未找到”结束i<=jm ?(i+j)2?j ?m-1对分查找流程图输入查找键key
m = (i + j)2
If d(m) = key Then
Label2.Caption = Str(m)
Exit Do '跳出循环
End If
If d(m) i = m + 1
Else
j = m – 1
End If
If语句格式Dim key As Integer, m As Integer, i As Integer, j As Integer
________________ '获得要查找数据key的值
________________ '分别对i,j赋初值
Do While i <= j
________________ ’求中间位置m的值
If d(m) = key Then
Label2.Caption = Str(m)
Exit do
End If
If d(m) < key Then
________________ ’求i的值
Else
________________ ’求j的值
End If
Loop
If i > 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) 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循环语句主要用于循环次数已知的情况下返回