对分查找算法复习精ppt课件

.,课题：对分查找算法复习,.,对分查找算法,一、生活中的对分查找,淘宝网上热卖的终极飞翼擎天柱（猜价格游戏）,.,游戏规则如下：（1）在给出这个玩具的价格是在100到200之间的整数。（2）竞猜价格时，先猜100-200之间的中间价格，如果太小了，就猜150200之间的中间价格，依此类推直到猜对为止。我来试试（我愿意一试）150太小175太大163太小169太小172太大170恭喜您猜对了,.,二、“对分思想，验证奇迹”,1.对分查找的基本思想：,（1）前提：被查找的数据序列必须是有序的。（2）基本思想：在有序的数据序列中（一般放在数组中），首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。,验证奇迹：对分查找实际数据演示动画,.,3.算法的基本框架：说明：要查找的数为key，待查找的数存在数组d中。i为查找范围的起点，j为查找范围的终点，m为范围i,j的中间位置，find为查找成功与否的标记，find为true代表查找成功；find为false代表查找失败。i=1j=16find=false查找的结果，若为true表示找到，若为false表示未找到dowhile(id(m)，则重新调整查找范围i=m+1i,j若keyj,3.对分查找算法的最多查找次数：,4.对分查找算法的实际意义：对分查找的高效性。（1）一个包含一百万个人名的电话簿中找一个名字，对分查找可以让你不超过20次就能找到指定的名字。（2）将全国13亿人按身份证号排列后，你可在31次比较后找到这个人的信息。,若用顺序查找还有这个效率吗？,假设每次对分最坏情况，直到最后一次才找到就会有2k=n/2得到k=long2n+1；二分法每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以+1。,.,六、“夯实基础，查漏补缺”,某8位男生的肺活量数据放在数组元素a(1)到a(8)中，其数据依次为：3205、3408、3471、3498、3621、3829、4233、4540，使用对分查找，设定查找键key，若第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是（）A、3408B、3829C、4233D、4540,2.某数组有7个元素，依次为200、202、204、205、210、215、218,若采用对分查找在该数组中查找数据200，需要查找的次数是（）若采用顺序查找数据200，需要查找的次数是（），这能说明顺序查找算法比对分查找算法效率高吗？。A、1B、2C、3D、4,3.我们育才高中在校生大约有1500人，学号有序排列，若现在利用对分查找来查找你的学号，最多需要查找（）次就能找到你自己。A、10B、11C、12D、13,.,4.还原高考医保卡余额查询，小朱设计了某单位医保卡余额查询系统，输入卡号，可以查出该卡号对应的余额。该单位共有n(n500)名职工，所有职工的医保卡号码和相应的余额等数据存放在数据库文件“company.accdb”的worker表中，程序界面如图所示，左边列表框List1中显示的是全部职工的卡号、姓名和余额，在文本框Text1中输入职工的卡号，单击“查询余额”按钮（Command1）后，如果找到此卡号，则在标签Label5中显示“此人的卡号、姓名和余额”，如果未找到则显示“找不到此卡号，请重新输入”。,.,程序实现代码如下：Dimkh(1To500)AsLongkh用于存储卡号Dimnam(1To500)AsStringnam用于存储职工姓名Dimye(1To500)AsSingleye用于存储医保卡余额Dimn,i,jAsIntegerPrivateSubForm_Load()数据库链接与打开代码略从数据库中读取每条记录的卡号、姓名、余额分别存于kh、nam、ye数组中DoWhilenotrs.EOFn=n+1kh(n)=rs.Fields(卡号)nam(n)=rs.Fields(姓名)ye(n)=rs.Fields(余额)rs.movenextLoop,.,将从数据库中读取出来的数据按余额升序排序Fori=1Ton-1Forj=nToi+1Step-1Ifkh(j)kh(j-1)Thent=kh(j):kh(j)=kh(j-1):kh(j-1)=tk=nam(j):nam(j)=nam(j-1):nam(j-1)=kp=ye(j):ye(j)=ye(j-1):ye(j-1)=pEndIfNextjNextIList1.AddItem本单位共有+Str(n)+名职工Fori=1TonList1.AddItemStr(kh(i)+nam(i)+Str(ye(i)Nexti,.,实现对卡号的查询，并显示所找到的卡号的医保卡余额PrivateSubCommand1_Click()Dimx,mAsIntegerDimfAsBooleanx=Val(Text1.Text)i=1j=nf=FalseDoWhile(i=j)andfm=(i+j)/2Ifx=kh(m)Then.ElseIfxkh(m)Then.Elsei=m+1EndIfLoopIff=TrueThenLabel5.Caption=卡号：+Str(kh(m)+姓名：+nam(m)+余额为：+Str(y