37对分查找算法及程序实现课件.ppt

1、3.7 对分查找算法及程序实现对分查找算法及程序实现1对分查找的概念对分查找的概念对分查找又称二分查找，是一种高效的查找方法。对分对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是，被查找的数据序列是有序的查找的前提是，被查找的数据序列是有序的(升序或降序升序或降序)。对分查找的基本思想是在有序的数列中，首先将要查找对分查找的基本思想是在有序的数列中，首先将要查找的数据与有序数列内处于中间位置的数据进行比较，如果两的数据与有序数列内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则就根据数据的有序性，再确定该者相等，则查找成功；否则就根据数据的有序性，再确定该数据的范围应该在

2、数列的前半部分还是后半部分；在新确定数据的范围应该在数列的前半部分还是后半部分；在新确定的缩少范围内，继续按上述方法进行查找，直到找到要查找的缩少范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，如果要查找的数据不存在，即查找不的数据，即查找成功，如果要查找的数据不存在，即查找不成功。成功。2对分查找的过程对分查找的过程若若key为查找键，数组为查找键，数组d存放存放n个已按升序排序的数据。在使用个已按升序排序的数据。在使用对分查找时，把查找范围对分查找时，把查找范围i，j的中间位置上的数据的中间位置上的数据d(m)与查找键与查找键key进行比较，结果必然是如下三种情况之一：进

3、行比较，结果必然是如下三种情况之一：(1)若若keyd(m)，由与，由与(1)相同的理由，必须在新的范围相同的理由，必须在新的范围(m1，j)中继续查找。中继续查找。这样，除了出现情况这样，除了出现情况(2)，在通过一次比较后，新的查找范围将，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。不超过上次查找范围的一半。中间位置数据中间位置数据d(m)的下标的下标m的计算方法：的计算方法：m(ij)2或或mfix(ij)/2)以规模为以规模为16的递增数组的递增数组d为例，观察对分查找的为例，观察对分查找的过程。要查找的数据过程。要查找的数据key为为37。3对分查找算法的表示对分查找算

4、法的表示使用对分查找在数组变量使用对分查找在数组变量d中查找中查找key，用自然语言描述，用自然语言描述的算法如下：的算法如下：(1)(确定初始查找范围确定初始查找范围)i1，jn。(2)(是否能继续查找？是否能继续查找？)如果如果ij，那么转到，那么转到(4)。(3)(找不到找不到)输入出结果输入出结果0，算法结束。，算法结束。(4)(计算中点位置计算中点位置)m(ij)2。(5)(相等？相等？)如果如果d(m)key，那么转到，那么转到(7)。(6)(修改查找范围修改查找范围)如果如果keyd(m)，那么，那么jm1；否则；否则im1，转到，转到(2)。(7)(找到找到)输出结果输出结果m

5、，算法结束。，算法结束。使用流程图描述对分查找的算法如下图所示：使用流程图描述对分查找的算法如下图所示：4对分查找算法程序的实现要点对分查找算法程序的实现要点(1)由于比较次数难以确定，所以用由于比较次数难以确定，所以用Do语句来实现循环；语句来实现循环；(2)在在Do循环体中用循环体中用If语句来判断查找是否成功；语句来判断查找是否成功；(3)若查找成功则输出查找结果，并结束循环若查找成功则输出查找结果，并结束循环(Exit Do)；(4)若查找不成功，则判断查找键在数组的左半区间还是若查找不成功，则判断查找键在数组的左半区间还是右半区间，从而缩小范围。右半区间，从而缩小范围。对分查找的程序

6、结构如下对分查找的程序结构如下(升序序列升序序列)：对分查找程序的基本框架：对分查找程序的基本框架：Private Sub Command1_Click()i 1:j n Do While i j m (i j)2 If d(m)Key Then 输出结果，退出查找输出结果，退出查找(代码略代码略)ElseIf Key d(m)Then j m 1 Else i m 1 End If LoopEnd Sub5.查找次数的估算查找次数的估算 对规模为对规模为n的数组进行对分查找时，无论是否找到，至的数组进行对分查找时，无论是否找到，至多进行多进行 log2n1(log2n表示大于或等于表示大于或

7、等于 log2n的最小整数的最小整数)次次查找就能得到结果，而使用顺序查找算法，在最坏的情况下查找就能得到结果，而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到查找键在最后一个或没找到)，需要进行，需要进行n次查找，最好的次查找，最好的情况是一次查找情况是一次查找(查找键在第一个查找键在第一个)，平均查找次数是，平均查找次数是 。21n本节的学习要求掌握对分查找算法的基本思想，掌本节的学习要求掌握对分查找算法的基本思想，掌握对分查找算法的程序实现要点，学会编写简单的对分握对分查找算法的程序实现要点，学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。查找的程序。掌握对

8、顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为对分查找算法在历次考试中出现的概率为90%以上，考以上，考查方式为选择题与填空题。查方式为选择题与填空题。1下列有关查找的说法，正确的是下列有关查找的说法，正确的是 ()A顺序查找时，被查找的数据必须有序顺序查找时，被查找的数据必须有序 B对分查找时，被查找的数据不一定有序对分查找时，被查找的数据不一定有序C顺序查找总能找到要查找的关键字顺序查找总能找到要查找的关键字 D一般情况下，对分查找的效率较高一般情况下，对分查找的效率较高D D 2某网站报名参加免费三亚游的会员序列号有：某网站报名参加免费三亚游的会员序列号有：101、1

9、35、238、342、450、558、633、708、846、910。采用对分查。采用对分查找，查找序列号为找，查找序列号为846号网友信息的过程中，依次被访问号网友信息的过程中，依次被访问的序列号是的序列号是()A450、708、846 B450、708、910、846C558、708、846 D558、708、910、846A A3某电子图书馆网站有某电子图书馆网站有10万本图书记录万本图书记录(已索引排序已索引排序)，假设，假设从中取出一条记录并与待查找项进行比较所花时间为从中取出一条记录并与待查找项进行比较所花时间为10毫毫秒，则用对分法在该系统中查找任意一本指定图书最多花秒，则用对分

10、法在该系统中查找任意一本指定图书最多花费的时间约为费的时间约为()A100万毫秒万毫秒 B50万毫秒万毫秒C10毫秒毫秒 D170毫秒毫秒D D 4某数组有某数组有7个元素，依次为个元素，依次为158、234、369、478、552、697、748。若采用对分查找法在该数组中查找数据。若采用对分查找法在该数组中查找数据748，需要查找的次数是需要查找的次数是 ()A1 B2C3 D4C C 5在有序单词序列：在有序单词序列：As、Book、Door、English、Floyd、Good、Hello、Sun中，用对分查找法找到单词中，用对分查找法找到单词“Good”所所需要的查找次数是需要的查找

11、次数是()A1 B2C3 D4B B 6某某8位男生的肺活量数据放在数组元素位男生的肺活量数据放在数组元素a(l)到到a(8)中，其数中，其数据依次为据依次为“3205、3408、3471、3498、3621、3829、4233、4540”。使用对分查找，设定查找键。使用对分查找，设定查找键key，若第一个被访，若第一个被访问到的数据是问到的数据是3498，小于，小于key值，则第二个被访问到的数据值，则第二个被访问到的数据是是 ()A3408 B3829C4233 D4540B B 7使用对分查找在已排序的数组使用对分查找在已排序的数组d(数组元素数组元素d(l)d(2)d(n)中查找中查找

12、key的算法流程图如下。其中、框中的的算法流程图如下。其中、框中的内容分别是内容分别是 ()Ajm1 im1 Bjm1 im1Cjm1 im1 Djm 1 im1C C 8有两组数据：有两组数据：54、31、43、12、8、73、56、34、89、60、23、6787、83、75、70、63、59、55、37、33、21、17、7下列有关查找方法描述不正确的是下列有关查找方法描述不正确的是 ()A可以直接使用顺序查找可以直接使用顺序查找 B可以直接使用对分查找可以直接使用对分查找C可以直接使用对分查找可以直接使用对分查找 D可以直接使用顺序查找可以直接使用顺序查找C C 9某查找算法的部分某查

13、找算法的部分VB程序代码如下：程序代码如下：t Falsei 0Do While i a(i+1)Then k k 1 Else k 1(1)If k max Then k=max(2)Next i Text2.Text Str(max)End Suba(i-1)11.某学校把每个学生的姓名和家长联系电话保存到计算机中，某学校把每个学生的姓名和家长联系电话保存到计算机中，以便遇到紧急情况时可以及时通知学生家长。每个学生的姓以便遇到紧急情况时可以及时通知学生家长。每个学生的姓名和家长联系电话已经保存在数组名和家长联系电话已经保存在数组xm和和phone(都为字符串类都为字符串类型型)中。现在要设

14、计一个根据输入的学生姓名查询该学生家中。现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序。程序运行时的界面如下图所示：长的联系电话的程序。程序运行时的界面如下图所示：完善程序：下列程序运行时，完善程序：下列程序运行时，在在Text1中输入学生姓名，单中输入学生姓名，单击击“查询家长电话查询家长电话”按钮按钮Command1后，在标签后，在标签Label2中显示对应的学生家长电话，中显示对应的学生家长电话，若找不到则显示若找不到则显示“未找到该学未找到该学生生”。程序代码如下：。程序代码如下：Dim xm(1 To 1000)As StringDim phone(1 To 1000

15、)As StringConst n As Integer 1000Private Sub Command1_Click()Dim x As String Dim find As Boolean Dim i As Integer x Text1.Text i 0 find False Do While(i n)And find False If Then find True Loop If find True Then Label2.Caption “该学生家长联系电话为：该学生家长联系电话为：”phone(i)Else Label2.Caption “未找到该学生未找到该学生”End IfEn

16、d Sub Private Sub Form_Load()学生姓名及家长电话数组赋初值语句，忽略学生姓名及家长电话数组赋初值语句，忽略End Sub请阅读代码并问答下列问题。请阅读代码并问答下列问题。(1)解决此问题的算法是解决此问题的算法是_。在程序和划线处填入适当的语句或表达式，将在程序和划线处填入适当的语句或表达式，将程序补充完整：程序补充完整：(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb33文件夹中。文件夹中。顺序查找算法顺序查找算法i=i+1x=xm(i)12某中学某中学200

17、9年下半年和年下半年和2010年上半年各有年上半年各有300名和名和100名名学生参加信息技术高考，下列学生参加信息技术高考，下列VB程序用于统计参加过这程序用于统计参加过这两次考试的学生信息，其中两次考试的学生信息，其中Command1_Click过程的算法过程的算法流程图如下所示：流程图如下所示：VB程序代码如下所示：程序代码如下所示：Dim a(1 To 300)As String用于存放用于存放2009年下年下半年考试学生的身份证号码半年考试学生的身份证号码Dim b(1 To 100)As String用于存放用于存放2010年上年上半年考试学生的身份证号码半年考试学生的身份证号码F

18、orm Load过程用于进行一些初始化准备工作过程用于进行一些初始化准备工作 Private Sub Form_Load()将参加将参加2009年下半年考试学生的身份证号码放在数年下半年考试学生的身份证号码放在数组组a中中将参加将参加2010年上半年考试学生的身份证号码放在数年上半年考试学生的身份证号码放在数组组b中中将数组将数组a中数据升序排列中数据升序排列将数组将数组a和数组和数组b中的数据分别显示在列表框中的数据分别显示在列表框List1和和List2中中代码略代码略End Sub请回答下列问题：请回答下列问题：(1)流程图中虚线框部分所采用的查找算法流程图中虚线框部分所采用的查找算法名

19、称是名称是_。(2)加框处代码有错，应改为加框处代码有错，应改为_。(3)加框处代码有错，应改为加框处代码有错，应改为_。Command1_Click()过程用于统计参加过这两次考试的学生信息过程用于统计参加过这两次考试的学生信息Private Sub Command1_Click()Dim i As Integer,bot As Integer,top As Integer,m As IntegerFor i=1 To 300 bot 1 top 300 Do While bot b(i)Then m=bot-1 Else bot m 1 End If LoopNext iEnd Sub对分

20、查找算法对分查找算法For i=1 to 100top=m-113按学号查找成绩。新生分班结束了，教务处将学生学按学号查找成绩。新生分班结束了，教务处将学生学号、学生班级和分班考试成绩录入到计算机中。为方便号、学生班级和分班考试成绩录入到计算机中。为方便学生查询录取情况，编制了一个根据学生学号查找某位学生查询录取情况，编制了一个根据学生学号查找某位学生所在班级及分班考试成绩的程序，如下图所示：学生所在班级及分班考试成绩的程序，如下图所示：程序运行后，同学可以自己输入自己的学号，然后单程序运行后，同学可以自己输入自己的学号，然后单击击“开始查找开始查找”按钮，计算机即可显示该同学的班级和成按钮，

21、计算机即可显示该同学的班级和成绩，如果学号错误，则显示绩，如果学号错误，则显示“未找到该学生信息未找到该学生信息”。实现该程序的部分代码如下：实现该程序的部分代码如下：Const n 100Dim xh(1 To n)As IntegerDim cj(1 To n)As SingleDim bj(1 To n)As StringDim x As IntegerFunction find(i,j)As Integer Dim m As Integer Do While i j m Fix(i j)/2)If xh(m)x Then find m Exit Function End If If x

22、 xh(m)Then j m 1 Else i m 1 End IfLoopfind 1End FunctionPrivate Sub Command1_Click()Dim i As Integer,j As IntegerDim k As Integer,c As Integer,s As StringDim r As Integer以学号为关键字对成绩表和班级表进行升序排序以学号为关键字对成绩表和班级表进行升序排序For i 1 To n 1 For j n To i 1 Step 1 If xh(j)xh(j 1)Thenk xh(j 1):xh(j 1)xh(j):xh(j)kc c

23、j(j 1):cj(j 1)cj(j):cj(j)cs bj(j 1):bj(j 1)bj(j):bj(j)s End If Next jNext iList1.ClearFor i 1 To 100 List1.AddItem Str(xh(i)“”bj(i)“”Str(cj(i)Next i根据输入的学号查找对应的班级和分班考试成绩根据输入的学号查找对应的班级和分班考试成绩r 1x Val(Text1.Text)x变量待查找学生序号变量待查找学生序号r find(1,n)If r 1 Then Text2.Text “未找到该学生信息未找到该学生信息”Else Text2.Text bj(

24、r)“”Str(cj(r)End IfEnd Sub Private Sub Form_Load()数组初始化语句，忽略数组初始化语句，忽略End Sub回答下列问题：回答下列问题：(1)程序中排序采用的是哪种排序算法？程序中排序采用的是哪种排序算法？_。(2)程序是查找采用的是哪种查找算法？程序是查找采用的是哪种查找算法？_。(3)显示查找结果的控件属于显示查找结果的控件属于_类，该控件的名称类，该控件的名称是是_。(4)如果有如果有100名同学的分班成绩存储在计算机中，现在名同学的分班成绩存储在计算机中，现在要查找按学号升序规律排在第要查找按学号升序规律排在第23位同学的分班情况及成绩，位

25、同学的分班情况及成绩，按照上述程序的查找算法，一共需要几次比较才能找到该同按照上述程序的查找算法，一共需要几次比较才能找到该同学的数据？学的数据？_。冒泡排序算法冒泡排序算法对分查找算法对分查找算法Text26文本框文本框14.小杨设计了某单位的公积金查询系统，输入职工的公积小杨设计了某单位的公积金查询系统，输入职工的公积金账号，可以查出该账号对应的余额。所有职工的公积金账号，可以查出该账号对应的余额。所有职工的公积金账号和相应的余额已分别保存在数组金账号和相应的余额已分别保存在数组a(按从小到大排按从小到大排序序)和数组和数组b中，第中，第i个职工的账号保存在个职工的账号保存在a(i)中，对

26、应的中，对应的账号余额保存在账号余额保存在b(i)中。中。程序界面如图所示，左边列表框程序界面如图所示，左边列表框List1中显示的是部分职中显示的是部分职工的账号和余额，在文本框工的账号和余额，在文本框Text1中输入职工的公积金账中输入职工的公积金账号，单击号，单击“查询余额查询余额”按钮按钮(Command1)后，如果找到此后，如果找到此账号，则在标签账号，则在标签Label2中显示中显示“此账号余额为此账号余额为”和账号对和账号对应的余额值，如果未找到则显示应的余额值，如果未找到则显示“找不到此账号，请重新找不到此账号，请重新输入输入”。解决此问题的算法流程图如图所示，相应的查找解决此

27、问题的算法流程图如图所示，相应的查找部分程序段如下：部分程序段如下：Dim a(1 To n)As LongDim b(1 To n)As SinglePrivate Sub Command1_Click()Dim x As Long,i As Long,j As Long,m As Long,f As Booleanx Val(Text1.Text)i 1:j n:f False 设账号总数为设账号总数为nDo While(i j)And Not f If x a(m)Then f True ElseIf x a(m)Thenj m 1 Else End IfLoopIf f ThenLab

28、el2.Caption “此账号余额为此账号余额为”Str(b(m)“元元”ElseLabel2.Caption “找不到此账号，请重新输入找不到此账号，请重新输入”End IfEnd SubPrivate Sub Form_Load()此过程用于对数组此过程用于对数组a和数组和数组b进行初始赋值，代码略进行初始赋值，代码略End Sub(1)解决此问题的算法是解决此问题的算法是_。在程序和划线处填入适当的语句或表达式，将程序补充完整：在程序和划线处填入适当的语句或表达式，将程序补充完整：(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。注：该示例程序

29、在素材文件夹下注：该示例程序在素材文件夹下vb35文件夹中。文件夹中。对分查找算法对分查找算法 m=Fix(i+j)/2)或或m=(i+j)2i=m+115.某生活超市货架上某生活超市货架上850件货是按价格从低到高进行件货是按价格从低到高进行001850编号的。某天，超市导购员要去找一本价格为编号的。某天，超市导购员要去找一本价格为56.80元元的商品。用的商品。用VB程序来模拟整个过程，已知在另一个事件程序来模拟整个过程，已知在另一个事件过程中，已经完成了过程中，已经完成了850件商品价格的录入，商品价格信件商品价格的录入，商品价格信息存放在数据息存放在数据a(1 to 920)中，在对象

30、中，在对象Text1中输入中输入56.80后，后，在对象在对象Label1上输出结果。上输出结果。部分程序代码如下：部分程序代码如下：Private Sub Command1_Click()key Val(Text1.Text)i 1:j 850：search 0Do While(i 0 Then Label1.Caption “在位置在位置”Str(search)“中找到该商品中找到该商品”Else Label1.Caption “找不到此价格商品找不到此价格商品”End IfEnd Sub(1)解决此问题的算法是解决此问题的算法是_。在程序和划线处填入适当的语句或表达式，将程序补充在程序和划线处填入适当的语句或表达式，将程序补充完整：完整：(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。对分查找算法对分查找算法(i+j)2keya(m)