浙教版信息技术选修1 5.4 查找算法的程序实现（共26张ppt)

课件26张PPT。　猜数小游戏规则：计算机随机给定一个1-128之间的整数，计算机会根据你猜的数提示你比该数是大了还是小了，直到猜中。看谁猜的最快！玩一玩对分查找算法
及程序实现（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=27第一次110522m=(i+j)2key=27第一次110522第二次610845d(m)keyd(m)=key任务一完成任务单上任务一表格的填写m=(i+j)2key=17第一次110522第二次14215第三次34317总结规律i的取值规律：j的取值规律：用对分查找算法查找数据（以升序数列为例）i=m+1j=m-1每次d(m)与Key比较会确定下一次查找范围找到了任务二完成任务单上任务二表格的填写m=(i+j)2key=40第一次110522第二次610845第三次67627第四次77735第五次87总结规律根据i，j的初值，计算出中间位置m，比较Key与d(m)，相等则输出，否则确定新i或新j，直到找到为止。
问：这样重复操作可以采用什么结构？循环结构继续进行重复查找的条件？i<=jN开始i?1,j?10d(m)？N继续查找？输出“未找到”结束i<=jm ?(i+j)2?j ?m-1对分查找流程图输入查找键keyi ?m+1任务三完成任务单上任务三代码的填写Dim key As Integer, m As Integer, i As Integer, j As Integer
Key=val(Text1.Text) '获得要查找数据key的值
i=1 : j=10 '分别对i , j赋初值
________________ ‘限定循环退出的条件
________________ ’求中间位置m的值
If d(m) = key Then
Text2.Text = "在d(" + Str(m) + ")中"
Exit Sub
End If
If d(m) < key Then
________________ ’求i的值
Else
________________ ’求j的值
End If
Loop
Text2.Text = "找不到" 任务三Dim key As Integer, m As Integer, i As Integer, j As Integer
Key=val(Text1.Text) '获得要查找数据key的值
i=1 : j=10 '分别对i , j赋初值
________________ ‘限定循环退出的条件
________________ ’求中间位置m的值
If d(m) = key Then
Text2.Text = "在d(" + Str(m) + ")中"
Exit Sub
End If
If d(m) < key Then
________________ ’求i的值
Else
________________ ’求j的值
End If
Loop
Text2.Text = "找不到" 对分查找算法程序实现Do While i<=jm=(i+j)2i=m+1j=m-1 如果查找的数据元素有n个，该怎么样改动程序？拓展任务一Dim key As Integer, m As Integer, i As Integer, j As Integer
Key=val(Text1.Text) '获得要查找数据key的值
i=1 : ‘ 分别对i , j赋初值
Do While i<=j ‘限定循环退出的条件
m=(i+j)2 ’求中间位置m的值
If d(m) = key Then
Text2.Text = "在d(" + Str(m) + ")中"
Exit Sub
End If
If d(m) < key Then
i=m+1 ’求i的值
Else
j=m-1 ’求j的值
End If
Loop
Text2.Text = "找不到" 对分查找算法程序实现j=10j=n 如果存储的数据是降序排列，该怎么样改动程序？拓展任务二Dim key As Integer, m As Integer, i As Integer, j As Integer
Key=val(Text1.Text) '获得要查找数据key的值
i=1 : j=n '分别对i , j赋初值
Do While i<=j ‘限定循环退出的条件
m=(i+j)2 ’求中间位置m的值
If d(m) = key Then
Text2.Text = "在d(" + Str(m) + ")中"
Exit Sub
End If
If d(m) < key Then

Else

End If
Loop
Text2.Text = "找不到" 对分查找算法程序实现i=m+1j=m-1i=m+1j=m-11、有序数列3,6,8,11,22,24,27,31,35,46用 对分法找31，需要（ ）次
A.4 B.3 C.2 D.1
2、有6位同学身高分别为165,170,172,175,176,180，其中小明身高为175，若采用对分法查找小明，则需要多少次找到 （ ）
A.2 B.3 C.4 D.5BB课堂练习3、小明在一次商品竞猜游戏中，采用了对分查找的算法进行猜价。当主办方出示了一件1000元以内商品后，小明第3次猜价时猜中了正确的价格。该商品的价格可能是（ ）
A、500 B、250 C、750 D、125D4、利用对分查找，在某校报名参加学生会主席竞选的学号列表20120101、20120135、20120238、20120342、20120450、20120558、20120633、20120708、20120846、20120910中，查找学号为20120846学生的过程中，依次被访问到的学号是（ ）
A、20120450、20120708、20120846
B、20120450、20120708、20120910、20120846
C、20120558、20120708、20120846
D、20120558、20120708、20120910、20120846A对分查找算法实施前提：有序数字序列
中点位置的计算：
(i+j)2 Int((i+j)/2) Fix((i+j)/2)
新的查找范围的确定
i=m+1 或者 j=m-1
查找结束的判定条件：找到数据或者i>j
对分查找算法的最多查找次数
由于对分查找过程中的每次比较都能使搜索范围减半，在N个数中查找，最多需要 Int(Log2N)+1 次找到目标值。