对分查找算法复习课件

《对分查找算法复习课件》由会员分享，可在线阅读，更多相关《对分查找算法复习课件（17页珍藏版）》请在金锄头文库上搜索。

1、课题：对分查找算法复习课题：对分查找算法复习 对分查找算法对分查找算法 一、生活中的对分查找一、生活中的对分查找 淘宝网上热卖的终极飞翼擎天柱（猜价格游戏） 游戏规则如下： （1）在给出这个玩具的价格是在100到200之间的整数。 （2）竞猜价格时，先猜100-200之间的中间价格，如果太 小了，就猜150200之间的中间价格，依此类推 直到猜对为止。 我来试试（我愿意一试） 150 太小 175 太大 163 太小 169 太小 172 太大 170 恭喜您猜对了 二、二、“对分思想，验证奇迹对分思想，验证奇迹” 1.对分查找的基本思想：对分查找的基本思想： （1）前提：被查找的数据序列必须

2、是有序的。 （2）基本思想： 在有序的数据序列中（一般放在数组中），首先把查 找的数据与数组中间位置的元素进行比较，若相等， 则查找成功并退出查找；否则，根据数组元素的有序 性，确定数据应在数组的前半部分还是在后半部分查 找；在确定了新的查找范围后，重复进行以上比较， 直到找到或未找到为止。 2. 验证奇迹： 对分查找实际数据演示动画 3. 算法的基本框架： 说明：要查找的数为key，待查找的数存在数组d中。i为查找 范围的起点，j为查找范围的终点，m为范围 i , j 的中 间位置，find 为查找成功与否的标记，find 为true代表 查找成功；find 为false代表查找失败。 i=

3、1 j=16 find=false 查找的结果，若为 true表示找到，若为 false表示未找到 do while (id(m) ，则重新调整查找范围i=m+1 i , j 若keyd(m)? 未找到，输出信息 找到，输出m 结束 N Y Y N Y N find=true? find=true Y N 三、“琢玉成形，化玉为器” 转化为程序代码 通过上述16个数据中查找key过程，程序代码如下： i=1 : j=16 : find=false Do while (id(m) then 表示待查数据比中间位置上的数大时 i=m+1 重新调整查找范围的起始位置 i=m+1 else 表示待查数

4、据比中间位置上的数小时 j=m-1 重新调整查找范围的终点位置 j=m-1 end if Loop If find then 判断查找的结果，若为 true表示找到，若为 false表示未找到 label1.caption= 找到！该数在数组中的位置为： + Str(m) else label1.caption= 未找到！该数在数组中不存在！“ end if 通过上述16个数据中查找key的过程，推广至n个数据中查找： i=1 : j=n : find=false Do while (id(m) then i=m+1 else j=m-1 end if Loop If find then ?氠

5、扡汥?慣瑰潩?尠找到！该数在数组中的位置为： + Str(m) else ?氠扡汥?慣瑰潩?尠未找到！该数在数组中不存在！“ end if 打开上机实践文件夹中的“对分查找.vpb” 文件，将窗体中“对分查找”按钮事件过程( Command3_Click() )中的代码补充完整。（注：带红色？处）并调试程序使之运行成功。 四、四、“体验之旅，感受程序魅力体验之旅，感受程序魅力” 1. 对分查找算法中被查找数据是降序的情况程序该如何修改？ i=1 : j=n : find=false Do while id(m) then . else . end if Loop If find then ?慬

6、敢?挮灡楴湯?找到！该数在数组中的位置为： + Str(m) else ?慬敢?挮灡楴湯?未找到！该数在数组中不存在！“ end if 五、五、“思想升华，化茧成蝶思想升华，化茧成蝶” 2.对分算法几个注意问题： （1）对分查找的前提：被查找数据必须是有序的。 （2）新的查找范围的确定：i=m+1 或 j=m-1 （3）查找结束的判断条件：找到数据(find=true)或 ij 3. 对分查找算法的最多查找次数： Log2n +1 4. 对分查找算法的实际意义：对分查找的高效性。 （1）一个包含一百万个人名的电话簿中找一个名字，对分 查找可以让你不超过20次就能找到指定的名字。 （2）将全国1

7、3亿人按身份证号排列后，你可在31次比较后 找到这个人的信息。 若用顺序查找还有这个效率吗？ 假设每次对分最坏情况，直到最后一次才找到 就会有 2k = n / 2 得 到 k = long2n + 1；二分法每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以+1。 六、“夯实基础，查漏补缺 ” 1. 某8位男生的肺活量数据放在数组元素 a(1)到a(8)中，其数据 依次为： 3205、3408、3471、3498、3621、3829、4233、 4540，使用对分查找，设定查找键 key，若第一个被访问到 的数据是3498，小于key值，则第二个被访问到的数据是（ ） A、

8、3408 B 、3829 C、4233 D、4540 2. 某数组有7个元素，依次为 200、202、204、205、210、215、218, 若采用对分查找在该数组中查找数据 200，需要查找的次数是（ ） 若采用顺序查找数据 200，需要查找的次数是（ ），这能说明顺序查找算法比对分查找算法效率高吗？ 。 A、1 B、2 C、3 D、4 3. 我们育才高中在校生大约有 1500人，学号有序排列，若现在利用 对分查找来查找你的学号，最多需要查找（ ）次就能找到你自己。 A、10 B、11 C、12 D、13 4. 还原高考 医保卡余额查询，小朱设计了某单位医保卡余额查询 系统，输入卡号，可以

9、查出该卡号对应的余额。该单位共有n (n500)名职工，所有职工的医保卡号码和相应的余额等数据存 放在数据库文件“ company.accdb”的worker 表中，程序界面如 图所示，左 边列表框List1中显示的是全部职工的卡号、姓名和 余额，在文本框 Text1中输入职工的卡号，单击“查询余额”按钮 （Command1）后，如果找到此卡号，则在标签 Label5中显示 “此人的卡号、姓名和余额”，如果未找到则显示“找不到此卡号， 请重新输入”。 程序实现代码如下：程序实现代码如下： Dim kh(1 To 500) As Long kh用于存储卡号 Dim nam(1 To 500) A

10、s String nam用于存储职工姓名 Dim ye(1 To 500) As Single ye用于存储医保卡余额 Dim n, i, j As Integer Private Sub Form_Load( ) 数据库链接与打开代码略 从数据库中读取每条记录的卡号、姓名、余额分别存于kh、nam、ye数组中 Do While not rs.EOF n = n + 1 ?桫渨?獲?敩摬? 卡号) ?慮?爠?楆汥獤尨 姓名) ?敹渨?獲?敩摬? 余额) rs.movenext Loop 将从数据库中读取出来的数据按余额升序排序 For i = 1 To n - 1 For j = n To i

11、 + 1 Step -1 If kh(j) kh(j - 1) Then t = kh(j): kh(j) = kh(j - 1): kh(j - 1) = t k = nam(j): nam(j) = nam(j - 1): nam(j - 1) = k p = ye(j): ye(j) = ye(j - 1): ye(j - 1) = p End If Next j Next I 楌瑳?摁?整?本单位共有?瑓?尠名职工 For i = 1 To n List1.AddItem Str(kh(i) + + nam(i) + + Str(ye(i) Next i 实现对卡号的查询，并显示所找到

12、的卡号的医保卡余额 Private Sub Command1_Click() Dim x, m As Integer Dim f As Boolean x = Val(Text1.Text) i = 1 j = n f = False Do While (i = j) and f m = (i + j) / 2 If x = kh(m) Then . ElseIf x kh(m) Then . Else i = m + 1 End If Loop If f = True Then 慌敢?灡楴湯?尠卡号：?瑓?桫洨?尠?姓名：?慮?尠?尠?尠余额为：?瑓?敹洨?尠元 Else ?扡汥?慃瑰潩?找不到此卡号，请重新输入 End If End Sub 请完成以下问题： （1）画虚线框部分所采用的算法是： （选择或冒泡） （2）程序中加框处有错，请改正： ； 。 （3）程序中画线部分应填入： ； 。