二分查找课件.ppt

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