资源描述
查找(search)是一种查询数据或信息的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。查询的方法很多，对不同的数据结构有不同的查找方法。例如，对以排序好的固定规模的数据序列进行查找时，其方法有对分查找等；对某些复杂的结构的查找，可用树型查找方法等等。查字典、查资料是我们经常进行的查找工作，在这里，是以在程序的某个数组变量中存储的一批数据内，寻找出特定的一个数据，或者确定在该数组内无这样的数据，作为查找的目的。通常，程序将按照查找的结果(找到或未找到)来决定执行后面的哪个计算步骤。,1、观察顺序查找的处理过程,假定被查找的数据（如8个）存储在有8个元素的数组变量 d 中，要寻找的数据（这个数据称为查找键）已经存储在变量 key 中。,顺序查找算法的输入输出说明,输入：查找键（设在变量 key 中）。,被查找的数据（设在数组变量 d 中）。,输出：若找到，结果是，值为 key 的数据所在的数组元素的下标。,未找到，结果是，0。,2、顺序查找算法流程图,m = 0 key = Int(InputBox(请输入要查找的数据，即查找键key值：, 对数组d进行顺序查找, 0) i = 1 Do While i = 8 If d(i) = key Then MsgBox 找到，数组下标值是： & i, 0, 顺序查找 m = 1 Exit Do End If i = i + 1 Loop If m = 0 Then MsgBox 未找到，结果是： & m, 0, 顺序查找 End If,3、顺序查找算法的VB编程代码(以规模为8的数组d举例),建立循环结构,从第一个元素开始遍历，逐个检验是否与查找键相等。,1、观察对分查找的处理过程,假定被查找的数据（如16个）存储在有16个元素的数组变量 d 中，并且，数组 d 是有序的（已经按非递减次序排列）。要寻找的数据（这个数据称为查找键）已经存储在变量 key 中。（参考P38图2.22）,对分查找算法的输入输出说明,输入：查找键（设在变量 key 中）。,被查找的数据（设在有序数组变量 d 中）。,输出：若找到，结果是，值为 key 的数据所在的数组元素的下标。,未找到，结果是，0。,对分查找的基本方法是：在查找范围（i，j）内，可以利用数据的有序性，而不必逐个数据地进行查找，进行简单地计算后，可得到查找范围的中点位置，并使用变量如m，记录这个中点位置。,把查找范围（i，j）的中点位置上的数据 dm 与查找键 key 进行比较，结果必然是如下三种情况之一：,（1） key dm 查找键小于中点处的数据 dm 。由数组d 中数据的递增性，可以确定：在（m，j）内不可能存在值为key 的数据，必须在新的范围（i，m-1）中继续查找。,（2） key = dm 查找键等于中点处的数据 dm 。找到了需要的数据。,（3） key dm 查找键大于中点处的数据 dm 。根据与（1）类似的理由，必须在新的范围（m+1，j）中继续查找。,因此，除了出现情况（2），在通过一次比较后，新的查找范围大约是原查找范围的一半。,举例观察图2.22对分查找过程中查找范围的变化。,d,i,m,j,第1次：初值 i1，j16，m8，key22,因 keydm，故（m，j）范围不存在值为key的数据。,int(i+j)/2)=int(1+16)/2),因key=22,dm=25,对分查找过程中查找范围的变化,8,金手指考试网 2016年金手指驾驶员考试科目一 科目四元贝驾考网 科目一科目四仿真考试题C1,Grammar,d,i,m,j,第2次：i1，j7，m4，key22,j=m-1=8-1=7,int(i+j)/2)=int(1+7)/2)=4,因 keydm，故（i，m）范围不存在值为key的数据。,因key=22，dm=8,对分查找过程中查找范围的变化,d,i,m,j,第3次：i5，j7，m6，key22,i=m+1=4+1=5,int(i+j)/2)=int(5+7)/2)=6,因 keydm，故（i，m）范围不存在值为key的数据。,对分查找过程中查找范围的变化,因key=22，dm=17,d,i，j，m,第4次：i7，j7，m7，key22,i=m+1=6+1=7,int(i+j)/2)=int(7+7)/2)=7,因 dm=key 故输出： “找到，数组下标值是：” & m,对分查找过程中查找范围的变化,因key=22，dm=22,对分查找过程中查找范围的变化,d,i,m,j,d,i,m,j,d,i,m,j,d,i，j，m,P38图2.22对分查找过程中查找范围的变化,2、对分查找算法的流程图,使用对分查找算法在具有n个数据的数组变量d中查找key时，因事先并不能确定比较的次数，但可以通过条件来控制重复是否继续进行。每进行一次比较后，当情况（1）(key dm )出现（即尚未找到key）时，应把原查找范围的一半作为新的查找范围，在这个新的范围内继续查找key。但这是需要前提的，即新的查找范围内必须至少有一个数据。由此得到的继续进行重复的条件是：,查找范围（i，j）中的数据个数,j-i+10,即,i=j,i = 1: j = n: b = 0 Do While i = j m = Int(i + j) / 2) If d(m) = key Then b = 1 Text2.Text = 找到，数组下标值是： & m Exit Do ElseIf d(m) key Then i = m + 1 Else j = m - 1 End If Loop If b = 0 Then Text2.Text = 未找到，结果是： & b End If,3、对分查找算法的VB编程代码(以规模为n的数组d举例),对分查找是先取中间元素和查找键比较，若不相等则缩小近一半的查找范围，在剩下的元素中继续查找。,循环初始值,实践体验,现代化学的元素周期律是1869年俄国科学家门得列夫(Dmitri Mendeleev)首创的，他将当时已知的63种元素依原子量大小并以表的形式排列，把有相似化学性质的元素放在同一行，就是元素周期表的雏形。利用周期表，门得列夫成功的预测当时尚未发现的元素的特性(镓、钪、锗)。1913年英国科学家莫色勒利用阴极射线撞击金属产生X射线，发现原子序越大，X射线的频率就越高，因此他认为核的正电荷决定了元素的化学性质，并把元素依照核内正电荷(即质子数或原子序)排列，经过多年修订后才成为当代的周期表。 在周期表中，元素是以元素的原子序排列，最小的排行最先。表中一横行称为一个周期，一列称为一个族。,1、主题（参考教材P39）,查找原子序数。,2、要求,元素周期表是化学学习中经常要使用的，通过查阅元素周期表，我们可以知道元素名称、元素符号、原子序数及原子量等信息。现在要求构建一个数组，按原子序数存放对应元素的元素符号。试设计一个算法，使得输入元素符号后，就能快速查找到对应的原子序数。,小结,1、掌握查找的概念；,2、顺序查找是按照数组元素的先后次序，从第一个元素开始进行遍历，逐个检验是否和查找键相等。,3、对分查找的前提是待查找的数据是有序的。对分查找是先取中间的元素和查找键比较，若不相等则缩小近一半的查找范围，在剩下的元素中继续查找。,4、对分查找的效率远高于顺序查找。,5、在数组中的查找结果，若找到，输出结果是，值为 key 的数据所在的数组元素的下标；若未找到，输出结果是，0。,
展开阅读全文