《对分查找算法复习PPT课件》由会员分享，可在线阅读，更多相关《对分查找算法复习PPT课件（17页珍藏版）》请在金锄头文库上搜索。
1、.,1,课题：对分查找算法复习,.,2,对分查找算法,一、生活中的对分查找,淘宝网上热卖的终极飞翼擎天柱（猜价格游戏）,.,3,游戏规则如下： （1）在给出这个玩具的价格是在100到200之间的整数。 （2）竞猜价格时，先猜100-200之间的中间价格，如果太 小了，就猜150200之间的中间价格，依此类推 直到猜对为止。 我来试试（我愿意一试） 150 太小 175 太大 163 太小 169 太小 172 太大 170 恭喜您猜对了,.,4,二、“对分思想，验证奇迹”,1.对分查找的基本思想：,（1）前提：被查找的数据序列必须是有序的。 （2）基本思想： 在有序的数据序列中（一般放在数组中
2、），首先把查 找的数据与数组中间位置的元素进行比较，若相等， 则查找成功并退出查找；否则，根据数组元素的有序 性，确定数据应在数组的前半部分还是在后半部分查 找；在确定了新的查找范围后，重复进行以上比较， 直到找到或未找到为止。,验证奇迹： 对分查找实际数据演示动画,.,5,3. 算法的基本框架： 说明：要查找的数为key，待查找的数存在数组d中。i为查找 范围的起点，j为查找范围的终点，m为范围 i , j 的中 间位置，find为查找成功与否的标记，find为true代表 查找成功；find为false代表查找失败。 i=1 j=16 find=false 查找的结果，若为true表示找到
3、，若为false表示未找到 do while (id(m)，则重新调整查找范围i=m+1 i , j 若keyd(m)，则重新调整查找范围j=m-1 i , j Loop 若find为真，表示查找成功，并输出找到的位置m； 若find为假，表示查找失败。,.,6,4. 对分查找算法的流程图实现：,请将补充完整： . . . .,.,7,三、“琢玉成形，化玉为器” 转化为程序代码,通过上述16个数据中查找key过程，程序代码如下： i=1 : j=16 : find=false Do while (id(m) then 表示待查数据比中间位置上的数大时 i=m+1 重新调整查找范围的起始位置 i
4、=m+1 else 表示待查数据比中间位置上的数小时 j=m-1 重新调整查找范围的终点位置 j=m-1 end if Loop If find then 判断查找的结果，若为true表示找到，若为false表示未找到 label1.caption= 找到！该数在数组中的位置为： + Str(m) else label1.caption= 未找到！该数在数组中不存在！“ end if,.,8,通过上述16个数据中查找key的过程，推广至n个数据中查找： i=1 : j=n : find=false Do while (id(m) then i=m+1 else j=m-1 end if Loo
5、p If find then label1.caption= 找到！该数在数组中的位置为： + Str(m) else label1.caption= 未找到！该数在数组中不存在！“ end if,.,9,打开上机实践文件夹中的“对分查找.vpb”文件，将窗体中“对分查找”按钮事件过程( Command3_Click() )中的代码补充完整。（注：带红色？处）并调试程序使之运行成功。,四、“体验之旅，感受程序魅力”,.,10,1. 对分查找算法中被查找数据是降序的情况程序该如何修改？,i=1 : j=n : find=false Do while id(m) then . else . end
6、 if Loop If find then label1.caption= 找到！该数在数组中的位置为： + Str(m) else label1.caption= 未找到！该数在数组中不存在！“ end if,五、“思想升华，化茧成蝶”,.,11,2.对分算法几个注意问题： （1）对分查找的前提：被查找数据必须是有序的。 （2）新的查找范围的确定：i=m+1 或 j=m-1 （3）查找结束的判断条件：找到数据(find=true)或 ij,3. 对分查找算法的最多查找次数：,4. 对分查找算法的实际意义：对分查找的高效性。 （1）一个包含一百万个人名的电话簿中找一个名字，对分 查找可以让你不
7、超过20次就能找到指定的名字。 （2）将全国13亿人按身份证号排列后，你可在31次比较后 找到这个人的信息。,若用顺序查找还有这个效率吗？,假设每次对分最坏情况，直到最后一次才找到就会有2k=n/2得 到k=long2n+1；二分法每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以+1。,.,12,六、“夯实基础，查漏补缺 ”,某8位男生的肺活量数据放在数组元素a(1)到a(8)中，其数据 依次为： 3205、3408、3471、3498、3621、3829、4233、 4540，使用对分查找，设定查找键key，若第一个被访问到 的数据是3498，小于key值，则第二个被访问
8、到的数据是（ ） A、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,.,13,4. 还原高考 医保卡余额查询，小朱设计了某单位医保卡余额查询
9、 系统，输入卡号，可以查出该卡号对应的余额。该单位共有n (n500)名职工，所有职工的医保卡号码和相应的余额等数据存 放在数据库文件“company.accdb”的worker表中，程序界面如 图所示，左 边列表框List1中显示的是全部职工的卡号、姓名和 余额，在文本框Text1中输入职工的卡号，单击“查询余额”按钮 （Command1）后，如果找到此卡号，则在标签Label5中显示 “此人的卡号、姓名和余额”，如果未找到则显示“找不到此卡号， 请重新输入”。,.,14,程序实现代码如下： Dim kh(1 To 500) As Long kh用于存储卡号 Dim nam(1 To 500
10、) As 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 kh(n) = rs.Fields(卡号) nam(n) = rs.Fields(姓名) ye(n) = rs.Fields(余额) rs.movenext Loop,.,15,将从数据库中读取出来的数据按余额升序排序
11、For i = 1 To n - 1 For j = n To i + 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 List1.AddItem 本单位共有 + Str(n) + 名职工 For i = 1 To n List1.AddItem Str(kh(i)
12、 + + nam(i) + + Str(ye(i) Next i,.,16,实现对卡号的查询，并显示所找到的卡号的医保卡余额 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 Label5.Caption = 卡号： + Str(kh(m) + + 姓名： + nam(m) + + 余额为： + Str(ye(m) + 元 Else Label5.Caption = 找不到此卡号，请重新输入 End If End Sub,.,17,请完成以下问题： （1）画虚线框部分所采用的算法是： （选择或冒泡） （2）程序中加框处有错，请改正： ； 。 （3）程序中画线部分应填入： ； 。,
