3.7对分查找算法及程序实现讲解.pptx

3.7 对分查找算法及程序实现;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。;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，算法结束。;使用流程图描述对分查找的算法如下图所示：;4．对分查找算法程序的实现要点 (1)由于比较次数难以确定，所以用Do语句来实现循环； (2)在Do循环体中用If语句来判断查找是否成功； (3)若查找成功则输出查找结果，并结束循环(Exit Do)； (4)若查找不成功，则判断查找键在数组的左半区间还是右半区间，从而缩小范围。;对分查找的程序结构如下(升序序列)：;对分查找程序的基本框架： 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 Loop End Sub;查找次数的估算 对规模为n的数组进行对分查找时，无论是否找到，至多进行 log2n＋1( log2n表示大于或等于 log2n的最小整数)次查找就能得到结果，而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到)，需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是 。;本节的学习要求掌握对分查找算法的基本思想，掌握对分查找算法的程序实现要点，学会编写简单的对分查找的程序。掌握对顺序查找与对分查找次数的估算。对分查找算法在历次考试中出现的概率为90%以上，考查方式为选择题与填空题。;;;;;;在一行数据(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程序如下，但加框处代码有错，请改正。;某学校把每个学生的姓名和家长联系电话保存到计算机中，以便遇到紧急情况时可以及时通知学生家长。每个学生的姓名和家长联系电话已经保存在数组xm和phone(都为字符串类型)中。现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序。程序运行时的界面如下图所示：;Dim xm(1 To 1000) As String Dim phone(1 To 1000) As String Const n As Integer ＝ 1000 Private 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 　 ①