二分法的动画演示课件.ppt

《二分法的动画演示课件.ppt》由会员分享，可在线阅读，更多相关《二分法的动画演示课件.ppt（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、二分查找二分查找沈阳市第二十中学沈阳市第二十中学 关坤关坤二二分查找分查找（对分查找）（对分查找）查找条件查找条件：被查找的数据必须是有序的。基本思想：基本思想：在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，或直到子表不存在，即查找不成功。思考思考A(lowA(low)A(highA(high)A(midA(mid)1low20mid 40highmid=int(low+high

2、)/2)mid=int(low+high)/2)Keya(mid)Keya(mid)Key=a(mid)Key=a(mid)找到了找到了要查找的数据是要查找的数据是 keykey思考思考A(1)A(1)A(40)A(40)A(20)A(20)1low20mid 40high 30mid40highA(1)A(1)A(40)A(40)A(21)A(21)21lowA(30)A(30)mid=int(low+high)/2)mid=int(low+high)/2)Keya(mid)Keya(mid)low=mid+1low=mid+1Keya(mid)Keya(mid)Keya(mid)low=m

3、id+1low=mid+1Keya(mid)Keya(mid)Keya(mid)low=mid+1low=mid+1Keya(mid)Keya(mid)Keya(mid)low=mid+1low=mid+1Keya(mid)Keyhigh Lowhigh 查找失败查找失败 Key=a(mid)Key=a(mid)找到了找到了要查找的数据是要查找的数据是 keykey开始开始定义数组变量定义数组变量key=A(mid)key=A(mid)？查找失败，或结束，或重新输入数据输入要查找的关键字输入要查找的关键字keykeymid=int(low+high)/2)mid=int(low+high)/2

4、)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

5、Command1_Click()Dim low,high,key,mid As IntegerDim low,high,key,mid As Integerlow=1:high=40:key=Val(Text1.Text)low=1:high=40:key=Val(Text1.Text)Do While low=highDo While low A(mid)key A(mid)Then Then?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二分查找二分查找一、查找条件：一、查找条件：有序数据有序数据二、基本思想二、基本思想1.1.循环，满足条件：循环，满足条件：low=highlowhighlowhigh，查找失败查找失败