5.4 查找算法的程序实现课件（15张PPT）

课件15张PPT。5.4 查找算法的程序实现浙江教育出版社 《算法与程序设计》游戏：商品价格竞猜第一组（方法甲）：
猜商品甲，只告诉对方猜的是“正确”还是“错误”，直到猜中为止。
第二组（方法乙）：
猜商品乙，如果没猜中，告诉对方“大了”还是“小了”，直到猜中为止。
想一想：
这两种方法有什么不同？哪种方法更快捷一些？采用这两种方法的前提是什么？
查找算法的程序实现二分查找二分查找（对分查找）查找条件：
被查找的数据必须是有序的。
基本思想：
在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，或直到子表不存在，即查找不成功。 超市商品价格查询系统流程图High = mid - 1Low = mid + 1low、high、mid表示待查找数据的位置，即数组元素的下标。注意：程序 代码Private Sub Command1_Click( )
Dim low, high, key, mid As Integer
low = 1: high = 30:key = Val(Text1.Text)
Do While low <= high
mid = Int((low + high) / 2)
If key = A(mid) Then： Text2.Text = "该商品价格为: " & b(mid) &“元”
****** ‘退出循环
ElseIf key > A(mid) Then： ? ? ? ? ? ?
Else
$ $ $ $ $ $
End If
Loop
If # # # # # # Then
Text2.Text= “ 找不到该商品，请重新输入条形码“ : Text1.Text = ""
End Sublow > highExit Dolow = mid + 1high = mid - 1超市商品价格查询系统程序 代码Private Sub Command1_Click( )
Dim low, high, key, mid As Integer
low = 1: high = 30:key = Val(Text1.Text)
Do While low <= high
mid = Int((low + high) / 2)
If key = A(mid) Then ： Text2.Text = "该商品价格为: " & b(mid) &“元”
****** ‘退出循环
ElseIf key > A(mid) Then： ： ? ? ? ? ? ?
Else
$ $ $ $ $ $
End If
Loop
If # # # # # # Then
Text2.Text = “ 找不到该商品，请重新输入条形码“ : Text1.Text = ""
End Sublow > highExit Dolow = mid + 1high = mid - 1Label3.CaptionLabel3.Caption
美化运行界面
编写代码
调试运行
拓展练习：挑战1：
如果在代码中引进布尔变量，怎样来完成“查找失败”部分的代码设计？
加油！期待你挑战成功！！！
程序 代码Private Sub Command1_Click( )
Dim low, high, key, mid As Integer
low = 1: high = 30:key = Val(Text1.Text)
Do While low <= high
mid = Int((low + high) / 2)
If key = A(mid) Then： Label3.Caption = "该商品价格为: " & b(mid) &“元”
Exit Do ‘退出循环
ElseIf key > A(mid) Then： low = mid + 1
Else
high = mid - 1
End If
Loop
If low > high Then
Label3.Caption = “ 找不到该商品，请重新输入条形码“ : Text1.Text = ""
End Subflag=falseflag=true : Exit Do ‘退出循环: Dim flag as boolean: flag=false

作品展示
拓展练习：
挑战2：
有兴趣的同学可以将此查询系统进一步改进，设计成超市收银台的收款系统。
加油！期待你挑战成功！！！
小结二分查找
一、查找条件：有序数据
二、基本思想
1.循环，满足条件：low<=high
①计算查找区域的中间位置：mid=int((low+high)/2)
②确定新的查找区域（key与 A(mid)比较）：
若相等，则查找成功,退出循环
若大于，则在后半区域继续查找，low=mid+1
若小于，则在前半区域继续查找，high=mid-1
2.如果low>high，查找失败
三、程序实现
分析问题→设计算法→编写代码→调试运行