3.7对分查找算法及程序实现

3.7对分查找算法及程序实现1．对分查找的概念对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是，被查找的数据序列是有序的(升序或降序)。对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩少范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不成功。2．对分查找的过程若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把查找范围[i，j]的中间位置上的数据d(m)与查找键key进行比较，结果必然是如下三种情况之一：(1)若keyd(m)，查找键小于中点d(m)处的数据。由数组d中的数据的递增性，可以确定：在(m，j)内不可能存在值为key的数据，必须在新的范围(i，m－1)中继续查找；(2)key＝d(m)，找到了需要的数据；(3)keyd(m)，由与(1)相同的理由，必须在新的范围(m＋1，j)中继续查找。这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。中间位置数据d(m)的下标m的计算方法：m＝(i＋j)\2或m＝fix((i＋j)/2)。以规模为16的递增数组d为例，观察对分查找的过程。要查找的数据key为37。J-M-1i-M+1J-M-1i-M+1D(m)=45key=37取小区间D(m)=23key=37取大区间D(m)=32key=37取大区间D(m)=37＝key=37找到3．对分查找算法的表示使用对分查找在数组变量d中查找key，用自然语言描述的算法如下：(1)(确定初始查找范围)i←1，j←n。(2)(是否能继续查找？)如果i≤j，那么转到(4)。(3)(找不到)输入出结果0，算法结束。(4)(计算中点位置)m←(i＋j)\2。(5)(相等？)如果d(m)＝key，那么转到(7)。(6)(修改查找范围)如果keyd(m)，那么j←m－1；否则i←m＋1，转到(2)。(7)(找到)输出结果m，算法结束。说明：对分查找最多次数应该是log2n，取整后加1使用流程图描述对分查找的算法如下图所示：4．对分查找算法程序的实现要点(1)由于比较次数难以确定，所以用Do语句来实现循环；(2)在Do循环体中用If语句来判断查找是否成功；(3)若查找成功则输出查找结果，并结束循环(ExitDo)；(4)若查找不成功，则判断查找键在数组的左半区间还是右半区间，从而缩小范围。对分查找的程序结构如下(升序序列)：对分查找程序的基本框架：PrivateSubCommand1_Click()i＝1:j＝nDoWhilei＝jm＝(i＋j)\2Ifd(m)＝KeyThen'输出结果，退出查找(代码略)ElseIfKeyd(m)Thenj＝m－1Elsei＝m＋1EndIfLoopEndSubCommand1点击事件开始Command1点击事件结束设置第一数和第n数求中间数5.查找次数的估算对规模为n的数组进行对分查找时，无论是否找到，至多进行log2n＋1(log2n表示大于或等于log2n的最小整数)次查找就能得到结果，而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到)，需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是。21n本节的学习要求掌握对分查找算法的基本思想，掌握对分查找算法的程序实现要点，学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为90%以上，考查方式为选择题与填空题。1．下列有关查找的说法，正确的是()A．顺序查找时，被查找的数据必须有序B．对分查找时，被查找的数据不一定有序C．顺序查找总能找到要查找的关键字D．一般情况下，对分查找的效率较高D2．某网站报名参加免费三亚游的会员序列号有：101、135、238、342、450、558、633、708、846、910。采用对分查找，查找序列号为846号网友信息的过程中，依次被访问的序列号是()A．450、708、846B．450、708、910、846C．558、708、846D．558、708、910、846A3．某电子图书馆网站有10万本图书记录(已索引排序)，假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒，则用对分法在该系统中查找任意一本指定图书最多花费的时间约为()A．100万毫秒B．50万毫秒C．10毫秒D．170毫秒D4．某数组有7个元素，依次为158、234、369、478、552、697、748。若采用对分查找法在该数组中查找数据748，需要查找的次数是()A．1B．2C．3D．4C5．在有序单词序列：As、Book、Door、English、Floyd、Good、Hello、Sun中，用对分查找法找到单词“Good”所需要的查找次数是()A．1B．2C．3D．4B6．某8位男生的肺活量数据放在数组元素a(l)到a(8)中，其数据依次为“3205、3408、3471、3498、3621、3829、4233、4540”。使用对分查找，设定查找键key，若第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是()A．3408B．3829C．4233D．4540B7．使用对分查找在已排序的数组d(数组元素d(l)≤d(2)≤…≤d(n))中查找key的算法流程图如下。其中①、②框中的内容分别是()A．①j←m＋1②i←m＋1B．①j←m—1②i←m－1C．①j←m－1②i←m＋1D．①j←m＋1②i←m－1C8．有两组数据：①54、31、43、12、8、73、56、34、89、60、23、67②87、83、75、70、63、59、55、37、33、21、17、7下列有关查找方法描述不正确的是()A．①可以直接使用顺序查找B．②可以直接使用对分查找C．①可以直接使用对分查找D．②可以直接使用顺序查找C9．某查找算法的部分VB程序代码如下：t＝Falsei＝0DoWhilei7Andt＝Falsei＝i＋1Ifd(i)＝KeyThent＝TrueLoopIft＝FalseTheni＝0数组元素d(1)到d(7)的数据依次为“8、9、5、8、4、7、8”，当变量key的值为8时，运用该算法处理后，变量i的值是()A．1B．2C．4D．7A10.在一行数据(1、23、6、2、4、5、6、18、5、19)中，存在连续递增的数据序列(1、23)、(6)、(2、4,5、6、18)、(5、19)，其序列长度分别为2、1、5、2，则连续递增的数据序列长度最大值max＝5。寻找max的方法如下：从第二个数据开始，将该数与它的前一个数比较，如果该数大于它的前一个数，则k←k＋1，否则k←1，……；直到最后一个数据处理完成为止。在此过程中将k的最大值保存在变量max中。依据上述算法描述编写的VB程序如下，但加框处代码有错，请改正。max=kConstn＝10Dima(1Ton)AsInteger'Text1_KeyPress过程用于输入数据并将数据依次存放到数组a中PrivateSubText1_KeyPress(KeyAsciiAsInteger)'该过程代码略EndSubPrivateSubCommand1_Click()DimiAsIntegerDimkAsInteger'连续递增的数据序列长度DimmaxAsInteger'连续递增的数据序列长度最大值max＝1k＝1Fori＝2TonIfa(i)a(i+1)Thenk＝k＋1Elsek＝1'(1)IfkmaxThenk=max'(2)NextiText2.Text＝Str(max)EndSuba(i-1)(1)加框①处应填入______________。(2)加框②处应填入______________。11.某学校把每个学生的姓名和家长联系电话保存到计算机中，以便遇到紧急情况时可以及时通知学生家长。每个学生的姓名和家长联系电话已经保存在数组xm和phone(都为字符串类型)中。现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序。程序运行时的界面如下图所示：完善程序：下列程序运行时，在Text1中输入学生姓名，单击“查询家长电话”按钮Command1后，在标签Label2中显示对应的学生家长电话，若找不到则显示“未找到该学生”。程序代码如下：Dimxm(1To1000)AsStringDimphone(1To1000)AsStringConstnAsInteger＝1000PrivateSubCommand1_Click()DimxAsStringDimfindAsBooleanDimiAsIntegerx＝Text1.Texti＝0find＝FalseDoWhile(in)Andfind＝False①If②Thenfind＝TrueLoopIffind＝TrueThenLabel2.Caption＝“该学生家长联系电话为：”＋phone(i)ElseLabel2.Caption＝“未找到该学生”EndIfEndSubPrivateSubForm_Load()'学生姓名及家长电话数组赋初值语句，忽略EndSub请阅读代码并问答下列问题。(1)解决此问题的算法是_______________________。在程序①和②划线处填入适当的语句或表达式，将程序补充完整：(2)程序中①划线处应填入_____________________。(3)程序中②划线处应填入_____________________。注：该示例程序在素材文件夹下vb33文件夹中。顺序查找算法i=i+1x=xm(i)12．某中学2009年下半年和2010年上半年各有300名和100名学生参加信息技术高考，下列VB程序用于统计参加过这两次考试的学生信息，其中Command1_Click过程的算法流程图如下所示：VB程序代码如下所示：Dima(1To300)AsString'用于存放2009年下半年考试学生的身份证号码Dimb(1To100)AsString'用于存放2010年上半年考试学生的身份证号码'FormLoad过程用于进行一些初始化准备工作PrivateSubForm_Load()'将参加2009年下半年考试学生的身份证号码放在数组a中'将参加2010年上半年考试学生的身份证号码放在数组b中'将数组a中数据升序排列'将数组a和数组b中的数据分别显示在列表框List1和List2中'代码略EndSub请回答下列问题：(1)流程图中虚线框部分所采用的查找算法名称是____________。(2)加框①处代码有错，应改为___________。(3)加框②处代码有错，应改为___________。'Command1_Click()过程用于统计参加过这两次考试的学生信息PrivateSubCommand1_Click()DimiAsInteger,botAsInteger,topAsInteger,mAsIntegerFori=1To300'①bot＝1top＝300DoWhilebot＝topm＝Fix((bot＋top)/2)Ifa(m)＝b(i)Thenlist3.AddItema(m)ExitDoElseIfa(m)b(i)Thenm=bot-1'②Elsebot＝m＋1EndIfLoopNextiEndSub对分查找算法Fori=1to100top=m-113．按学号查找成绩。新生分班结束了，教务处将学生学号、学生班级和分班考试成绩录入到计算机中。为方便学生查询录取情况，编制了一个根据学生学号查找某位学生所在班级及分班考试成绩的程序，如下图所示：程序运行后，同学可以自己输入自己的学号，然后单击“开始查找”按钮，计算机即可显示该同学的班级和成绩，如果学号错误，则显示“未找到该学生信息”。实现该程序的部分代码如下：C