2020版信息技术新优化浙江大一轮（课件+优选习题）：第三部分 第三章　查找算法的程序实现 (共2份打包)

第三章　查找算法的程序实现 -2- -3- 考点1 考点2 顺序查找 查找是一种能以比较少的步骤或较短的时间找到所需对象的一种查询技术。常见的查找方法有顺序查找和对分查找。 顺序查找的基本思想:从第一个数据开始,按照数据的顺序逐个将数据与给定的值进行比较,若某个数据与给定值相等,则查找成功,找到所查数据的位置;反之,则查找不成功。顺序查找算法简单,对数据表中的元素是否有序没有要求,N个元素的顺序查找过程中数据比较的次数最多是N次。 顺序查找的程序结构: k=0(k用来保存与要查找数据key相等的元素的下标) 条目梳理 -4- 考点1 考点2 如果k≠0,则输出查找成功,否则输出查找不成功。 顺序查找程序段 k=0 for i=1 to n if a(i)=key then k=i next i if k<>0 then 输出查找成功 else 输出查找失败 end if 条目梳理 -5- 考点1 考点2 【例1】 在数组元素a(1)到a(8)中查找键值为key的数,其顺序查找的VB程序段如下,请在划线处填写正确的语句。 for i=1 to 8 if ①　　　　　　　　then  　　Text1.text=str(i) 　　exit for end if next i if ②　　　　　　　　then  text1.text=″在数组中没有找到″+str(key) end if 条目梳理 -6- 考点1 考点2 答案:①a(i)=key　② i>8 解析:根据顺序查找的基本思想,依次将数组元素a(1)到a(8)跟查找键值key比较,若相等,显示找到结果并退出循环,否则继续查找。程序实现时,变量i用来表示第几次查找,而a(i)则是第i次查找时被访问到的数组元素。如果某个数组元素a(i)的值等于key则将该数组元素的下标值i显示在text1文本框中,并通过exit for来结束查找。若没有找到key,则i的值必定大于8,故划线①处的条件表达式为“a(i)=key”,划线②处的条件表达式为“i>8”。 条目梳理 -7- 考点1 考点2 对分查找 对分查找又名二分查找,是一种高效的查找方法,但前提是被查找的数据必须是有序的。 1.对分查找的基本思想 首先将查找键与有序数组内处于中间位置的元素进行比较,如果相等表明查找成功;否则根据数据的有序性,确定应该在数组的前半部分还是后半部分继续查找,在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。对分查找最多进行[log2N]+1次查找。[log2N]表示小于等于log2N的最大整数。 2.对分查找实现的要点 (1)由于比较次数不确定,所以一般用do语句实现。 (2)在do的循环体中用if语句来判断是否查找成功。 (3)若查找成功则输出查找结果,并用exit for语句提前结束循环。 条目梳理 -8- 考点1 考点2 3.对分查找的程序结构(以查找升序序列为例) 条目梳理 -9- 考点1 考点2 4.常用对分查找程序段 i=1:j=n do while i<=j m=(i+j)\2 if a(m)=key then 　　'找到目标,退出查找 else if key<a(m) then 　　j=m-1 else 　　i=m+1 end if loop if　i>j then 　'未找到目标 end if 条目梳理 -10- 考点1 考点2 【例2】 小金设计了一个按原子量找元素名称和符号的VB程序。程序运行时,先将26种元素原子量按从小到大保存在数组a中,对应的元素名称和元素符号保存在数组b和c中,并在列表框List1中显示。然后在文本框Text1中输入一个原子量数值,单击“查找”按钮Command1,Label3中显示查找到的元素名称和符号,程序运行界面如图所示。 条目梳理 -11- 考点1 考点2 查找26个元素的程序代码如下,请在画线处填入合适代码: Dim a(1 To 26) As Single,b(1 To 26) As String,c(1 To 26) As String Private Sub Command1_Click() Dim i As Integer,j As Integer,m As Integer Dim k As Single,f As Booleam i=1:j=26:f=False k=Val(Text1.Text) Do While i<=j And Not f m=　①　  If k=a(m) Then 条目梳理 -12- 考点1 考点2 　　Label3.Caption=″元素:″+b(m)+″　″+　②　  　　f=True Else 　　If k<a(m)　Then 　　　　j=　③　  　　Else 　　　　i=m+1 　　End