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