数据查找（教学设计）高中信息技术选修1数据与数据结构（浙教版2019）

5.4数据查找（教学设计）年级高二年级授课时间2课时课题5.4数据查找教学目标1.了解数据查找的基本概念和常见算法。2.掌握顺序查找、二分查找等数据查找算法的原理和实现方法。3.能够分析和比较不同数据查找算法的优缺点。还能够应用所学知识解决实际问题。教学重难点重点：1.数据查找的基本概念和算法原理；2.顺序查找和二分查找算法的实现方法；3.不同数据查找算法的比较和应用。难点：1.理解二分查找算法的递归实现；2.分析不同数据查找算法的时间复杂度。教学准备多媒体课件、多媒体教室教学过程教师活动学生活动新课导入一、课堂导入1.通过几张图片展示：上下面两幅图片中有几处不同的地方，同学们能不能快速的找出来？下列5个图标找出哪一个是微信图标？能一眼看出来吗？生活中还有哪些查找的具体例子，你是通过什么样的方法快速进行查找的。在日常生活中，人们经常会进行各种查找操作，如在上查找公交车的线路、在电子词典中查找某个单词的读音和含义、在音乐网站上查找自己喜欢的音乐以及利用搜索引擎在浩瀚的信息海洋中查找需要的信息等。新知讲授一、查找1.概念查找（Search）又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。2.查找①没有找到满足条件的对象返回特定值，表明查找失败；②查找到满足条件的对象表明查找成功，一般要求返回该对象的存储位置或对象值本身。通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个计算步骤。如超市购物付款时，当收银员扫描一件货物的条形码时，计算机需要在几万条不同的记录中寻找这件商品，然后显示相应的商品名称和价格。二、常见的排序算法1.顺序查找（1）算法思想从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等，则查找成功，记录所查数据的位置；反之，则查找不成功。（2）算法特点①算法简单，对数据是否有序没有要求。②查找效率较低，当数据量大时不宜使用。（3）案例讲解以“在成绩查询系统中查找某学号”为例，假定某学习小组8名学生的学号数据存储在数组d中，要查询的学生学号（查找键）已经存储在变量key中。①算法演算从数组d的第1个元素d[0]开始，依次判断各元素的值是否与查找键key的值相等。若某个数组元素d[i]的值等于key，则结束处理（找到了指定的数据）；若找遍了所有8个元素，无任何元素的值等于key，则结束处理（未找到指定的数据）。在规模为8的数组d中，分别按顺序查找算法寻找数据18和15的情况，处理过程中找到的第4个数组元素d[3]中的数据与18相等，表示8个数据中存在值为18的元素；而若key为15时，查找完所有数据仍未找到，表示8个数据中不存在值为15的元素。顺序查找过程实例②顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为O(n)。顺序查找算法流程图③实现此算法的Python程序如下：d=[25,22,13,18,14,11,17,19]key=18flag=Falselength=len(d)foriinrange(length):ifd[i]==key:flag=Truebreakifflag==True:print("查找成功！")else:print("未找到")④顺序查找算法也可以写成函数的形式，如右表所示：defseq_search(s,a):length=len(s)flag=Falseforiinrange(length):ifs[i]==a:flag=Truebreakifflag==True:returnielse:returnFalsed=[25,22,13,18,14,11,17,19]key=15result=seq_search(d,key)print(result)（4）探讨与讨论①顺序查找算法的部分代码如下：Flag=Falsei=0whilei<5andFlag==False:i=i+1ifa[i]==key:Flag=TrueifFlag==False:i=0数组元素a=[8,7,3,5,4]，若key值为3，则运行该程序后，变量i的值是（）A.0 B.2 C.3 D.5②某查找算法的VB代码如下：k=0i=0whilei<=6:ifa[i]==key:k=ii=i+1数组元素a=[5,3,5,1,8,5,9]，当变量key值为5时，运用该算法处理后，变量k的值是()A.1 B.2 C.5 D.02.二分查找（1）算法思想二分查找（BinarySearch）又称折半查找、对分查找。首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。（2）算法特点①要求被查找数据必须有序。②查找效率非常高，适用于大数据查找。在数组中的数据是有序的，若是升序的，是指下标越小的数组元素中存储的数据也越小，降序则相反。（3）基本方法为简单起见，设数组d中存储了n个互不相同的数据，并且数组d中的数据是升序的，则应有：d[0]＜d[1]＜…＜d[n–2]＜d[n–1]。使用两个变量i和j分别记录查找范围内的第一个数组元素和最后一个数组元素的下标。开始时，整个数组中的所有n个元素都在查找范围内，即变量i的初值为0，j的初值为n–1，用(i,j)表示查找范围从d[i]起到d[j]为止。二分查找的基本方法是：在查找范围(i,j)内，可以利用数据的有序性，而不必逐个地进行查找。①首先确定该区间的中点位置：m=(i+j)/2」（m表示小于等于的最大整数）。②然后将查找键key与d[m]比较，结果必然是如下三种情况之一：(a)key＜d[m]，查找键小于中点d[m]处的数据。因为数组d中的数据递增，可以确定在(m,j)内不可能存在值为key的数据，所以只需在新的范围(i,m–1)中继续查找。(b)key=d[m]，找到了需要的数据。(c)key＞d[m]，由与（a）相同的理由，只需在新的范围(m+1,j)中继续查找。在通过一次比较后，新的查找范围不会超过上一次查找范围的一半。（4）案例讲解以规模为11的数组d为例，观察二分查找的过程。在数组d的11个元素中，已按增序存储了11个数据，要寻找的数据为12（已存储在变量key中）。①算法演算初，数组d中的11个元素（从d[0]到d[10]）都在查找范围内，中点处的数组元素是d[5]。通过第1次比较（d[5]与key的比较）后发现，key的值比中点处的数据小，在数组d的右半部分（从d[6]到d[10]的范围）内不存在要找的数据，只需在数组d的左半部分（从d[0]到d[4]的范围）进行下一次查找。第2次比较时，中点处的数组元素是d[2]。比较后发现，第3次查找的范围为d[0]到d[1]，中点处的数组元素是d[0]。此时，key的值比中点处的数据大，第4次的查找范围只有一个元素，即d[1]，而d[1]的值与key的值相等，找到指定的数据。②查找过程中，查找范围的变化情况二分查找过程实例③在规模为n的数组d中进行二分查找的流程图二分查找算法流程图④实现此算法的Python程序如下：key=12d=[6,12,15,18,22,25,28,35,46,58,60]f=False#i和j定义子数组的边界，一开始搜索的是整个数组i=0j=len(d)–1whilei<=j:m=(i+j)//2ifd[m]==key:f=Trueb=mbreakifkey<d[m]:#到左边去找j=m–1else:#到右边去找i=m+1iff==True:print("查找成功！第"+str(b)+"个")else:print("没有找到！")（5）拓展链接：二分查找算法的递归实现二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍整个序列。①二分查找算法可利用递归来实现，程序如右表：defbsearch(s,array):iflen(array)==0:print("未找到！")returnFalsemid=(len(array)–1)//2ifarray[mid]==s:print("找到了！")returnTrueelifs<array[mid]:returnbsearch(s,array[:mid])else:returnbsearch(s,array[mid+1:])key=12d=[6,12,15,18,22,25,28,35,46,58,60]print(bsearch(key,d))②二分查找与二叉树❊二分查找过程可用一棵二叉树来描述，树中的每个根节点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表。通常把此树称为二分查找的判定树。❊在有序表上二分查找一个关键字等于key的元素时，对应着判定树中从根节点到待查节点的一条路径，与关键字进行比较的次数就等于该路径上的节点数，或者说等于待查节点的层数。❊查找key为12的元素时，从根节点到待查节点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即log2n」+1。❊由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。二分查找的判定树实例（6）拓展链接：二叉排序树二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。①排序二叉排序树的排序功能主要通过二叉树的建立和遍历过程来实现，其在建立过程中要始终满足如下性质：（a）若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。（b）若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。（c）它的左右子树也分别为二叉排序树。一组数据“23，20，13，18，14，11”建立的二叉排序树如右图所示，对此二叉树进行中序遍历时，结果为从小到大的有序序列：11，13，14，18，20，23。二叉排序树②查找二叉查找树的查找过程为：首先将给定值和根节点的关键字比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在左子树或右子树中继续进行查找。若查到为空树时，说明该树中没有待查记录，故查找不成功。在上图中所示的二叉查找树中查找关键字key为14的节点，则查找过程为：（a）先将数据14与根节点中的数据23比较，由于14小于23，则在左子树中继续查找。（b）将数据14与节点数据20比较，由于14小于20，则在左子树中继续查找。（c）将数据14与节点数据13比较，由于14大于13，则在右子树中继续查找。（d）同样的方法继续查找，当找到节点数据14时，与要查找的数据相等，则查找成功。（7）探讨与讨论①用对分查找从数列3、6、7、10、12、16、25、30、75中查找数据10，则依次访问的数据为()A.12、6、7、10 B.12、7、10C.12、6、10 D.12、7、6、10②某二分查找算法的程序如下：i＝0j＝7n＝10whilei<＝j：n＝n＋1m＝(i＋j)//2ifkey＝＝d[m]：breakelifkey>d[m]：j＝m－1else：i＝m＋1数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是()A.62或16B.62或27C.75或27D.75或16三、排序算法的应用查找算法在实际生活中的应用航空公司VIP会员积分查询：不少航空公司都会提供优惠的会员服务，当某会员飞行里程累积达到一定数量后，可以使用里程积分兑换奖励机票或奖励升舱等服务。现给定某航空公司部分VIP会员的飞行里程、积分等信息，要求实现根据VIP号码快速查询会员积分的功能。某航空公司的部分会员信息表1.抽象与建模从表中的数据可以看出，每个会员的信息是一条记录，包括VIP号、姓名、飞行里程、积分等数据项。要显示某个会员的积分信息，先得从多条记录中查找到该会员的记录，如下所示：若用a[i]表示该条记录，则该会员的积分可采用以下形式表示：a[i][3]（表示该条记录的第4个数据项的值）2.设计算法与数据结构对表格数据可采用4个一维数组按列或1个一维数组按行来存储。要显示某个会员的积分，先要从多条会员信息的数据中找到该会员。查找可采用顺序查找算法或二分查找算法。从算法的时间复杂度方面考虑，二分查找算法的效率高于顺序查找算法，但若采用二分查找算法，被查找的数据序列必须是有序的，即要按VIP号为关键字进行排序。3.编写程序(1)假如数据以1个一维数组按行来存储，利用二分查找算法查找，程序如下：importcsv#数据读入csvFile=open("vip.csv","r")reader=csv.reader(csvFile)a=[]foriteminreader:a.append(item)csvFile.close()#排序defbubble_sort(d):foriinrange(1,len(d)):forjinrange(1,len(d)–i):ifint(d[j][0])>int(d[j+1][0]):temp=d[j]d[j]=d[j+1]d[j+1]=temp#二分查找defbsearch(s,array):i=1#查找范围不包含第一行数据j=len(array)–1whilei<=j:m=(i+j)//2ifint(array[m][0])==s:returnmifs<int(array[m][0]):j=m–1else:i=m+1return–1#未找到返回–1bubble_sort(a)key=int(input('请输入要查询的VIP号：'))m=bsearch(key,a)ifm!=–1:print(a[m][1],"先生/女士，您的积分为：",a[m][3])else:print('找不到VIP号对应的用户信息！')运行程序，当输入VIP编号“600815”时，程序输出“李亚东先生/女士，您的积分为：436”的信息。4.探讨与讨论四、课堂小练五、小结1.查找(1)概念(2)条件2.常见的查找算法(1)顺序查找①算法思想②算法特点③算法演算(2)二分查找①算法思想②算法特点③算法演算(3)拓展链接①二分查找算法的递归实现②二叉排序树3.查找算法的应用(1)案例讲解①抽象与建模②设计算法与数据结构③编写程序“在成绩查询系统中查找某学号”为例，通过算法演算，深入浅出的解析这一过程。实现此算法的Python程序。顺序查找算法，那么同学们可以将其写成函数的形式，后续直接调用即可。深入浅出的解析这一过程。实现此算法的Python程序。拓展链接，二分查找算法的递归实现，在此基础上，加深对二分查找的理解，融入递归的知识，与之前章节的知识先后呼应。将二分查找与二叉树进行结合，让学生更好的理解二分查找。拓展链接，二叉排序树，在此基础上，加深对二分查找的理解，融入二叉树的知识，与之前章节的知识先后呼应。将排序算法的应用进行抽象化的展示，通过生活中的例子：航空公司VIP会员积分查询，这一案例的讲解，从三个方面循序渐进的深入解析，抽象与建模让学生理解Python中的查找函数如何解决实际中的问题，然后设计算法与数据结构让学生体验用Python中的查找函数解决问题的基本流程，最后编写程序，逐步形成运用Python中的查找函数解决问题的思维方式和学科方法。按照由粗到细、逐步求精的策略,推动学生加深对顺序查找、二分查找的深刻认识。课堂练习（有题有答案有解析）1.查找又称，计算机根据所给条件查找出满足条件的对象，即寻找出，或者确定在该批数据内是否存在这样的数据。2.若没有找到满足条件的对象，则返回特定值，表明查找；若查找到满足条件的对象，则表明查找，一般要求返回。3.顺序查找又称，从的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。4.顺序查找将待查找的数值与序列中的数，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为。5.二分查找又称、。它是一种效率很高的查找方法，但被查找的数据序列必须是。二分查找首先将查找键与内处于位置的元素进行比较，如果中间位置上的元素的数值与查找键，根据数组元素的有序性，就可确定在数组的还是继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。6.二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍。7.二分查找过程可用来描述，树中的每个根节点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，通常把此树称为。8.二叉排序树的排序功能主要通过二叉树的和过程来实现。9.二叉查找树的查找过程为：首先将给定值和根节点的比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在或中继续进行查找。若查到为时，说明该树中没有待查记录，故查找不成功。10.给定任意的查找键，在序列3,5,8,12,15,23中进行数据查找，下列说法不正确的是（）A.若用顺序查找实现，则最少查找1次B.若用二分查找实现，则最少查找1次C.若用顺序查找实现，则最多查找6次D.若用二分查找实现，则最多查找4次11.若线性表采用链式存储结构，则适用的查找方法为()。A.随机查找B.散列查找C.二分查找D.顺序查找参考答案：1.检索、在存储的一批数据内、一个特定的数据2.失败、成功、该对象的存储位置或对象值本身3.线性查找、顺序表4.顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为O(n)。5.折半查找、对分查找、有序的、有序数组、中间位置、不同、前半部分、后半部分6.整个序列7.一棵二叉树、二分查找的判定树。8.建立、遍历9.关键字、左子树、右子树、空树10.答案：D[解析]顺序查找时从头到尾逐个查找，数组中共有6个元素，所以最少可能一次找到，最多数组每个元素查找一遍共六次;二分查找查找的最多次数为logzn+1次，由于数组共有6个元素，所以最多查找次数为3次，最少为1次。综合以上信息，D项说法错误故选:D。11.答案：A[解析]随机查找表中元素时，访问表中任一元素所需时间与元素的位置和排列次序无关。以散列方式存储和查找数据时，元素的存储位置与其关键字相关。二分法查找只能在有序顺序表中进行。由于链表中的元素只能通过取得元素所在的节点的指针进行，因此只能顺序查找表中的元素。课堂小结课堂小结一、查找1.概念2.条件二、常见的查找算法1.顺序查找（1）算法思想（2）算法特点（3）算法演算2.二分查找（1）算法思想（2）算法特点（3）算法演算3.拓展链接（1）二分查找算法的递归实现（2）二叉排序树三、查找算法的应用1.案例讲解（1）抽象与建模（2）设计算法与数据结构（3）编写程序作业设计1.某数组有10个元素，依次为10、23、32、40、55、64、77、81、93、100，若采用对分查找法在该数组中查找数据93，依次被访问的数据为()A.64、81、92B.55、77、81、93C.55、81、93D.64、81、100、932.数组里有12个元素，依次为:34、40、41、43、53、55、65、70、72、74、80、95，下列选项中不正确的是()A.如使用顺序查找法，53需要查找5次B.如使用对分法查找，53需要查找3次C.如使用顺序查找法，70需要查找8次D.如使用对分法查找，70需要查找4次3.分别使用顺序查找算法和二分查找算法在数据序列“5,6,10,13,15,20,21.26,30”中查找数据10,下列关于查找的次数的说法中正确的是A.顺序查找2次,二分查找3次B.顺序查找3次,二分查找2次C.顺序查找3次,二分查找3次D.顺序查找3次,二分查找4次4.在10个有序的数“21,45,56,65,68,72,79,83,88,96"中查找75,则依次需要进行比较的数据是（）A.68，83，72B.21，45，56，65，68，72，79C.68，83，72，79D.68，45，56，655.在7个有序的数列“1，2，3，4，5，6，7”中，采用二分查找法查找数值key，依次需要进行比较的数据可能是()A.4B.4，6，2C.4，2，5D.4，6，5，76.下列有关查找的说法中，正确的是()A.顺序查找时，被查找的数据必须有序B.对分查找时，被查找的数据不一定有序C.顺序查找总能找到要查找的关键字D.一般情况下，对分查找的效率较高7.下列有关查找的说法中,不正确的是（）A.采用顺序查找时,被查找的数据集中的元素无须有序B.采用二分查找时,被查找的数据集中的元素必须有序C.二分查找总能找到要查的键值D.二分查找的效率通常比顺序查找高8.下列有关查找的说法，正确的是（）A.进行对分查找时，被查找的数据必须已按升序排列B.进行对分查找时，若查找的数据不存在，则无须输出结果C.在《新华字典》中查找某个汉字，最适合使用顺序查找D.对规模为n的数据进行顺序查找，平均查找次数是9.运用二分查找算法可以提高查找的效率，前提是待查找序列必须是()排序的。A.递增B.递减C.有序D.无序10.已知单调函数f()在[0,1]区间上存在一个x0，使f(x0)=0。现用对分查找法搜索x0的值，开始搜索区间为[0,1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为（）A.B.C.1/102D.1/21011.8位同学的语文数学成绩总分从高到低为“178，176，173，172，170，168，163，160。用二分查找法178的过程中，依次被访问到的成绩数据是()A.178B.172，176，178C.172，173，178D.172，173，176，17812.7位学生的身高(单位cm)从高到低依次为:178，177，175，172，170，165，162.用对分查找法找到178的过程中，依次被访问到的数据是（）A.178B.172，175，178C.172，177，178D.172，175，177，17813.某数组d中的数据依次是[8,12,15,28,28,32,36,39]，要查找某个元素是否在数组中，下列说法正确的是()A.数组中有相同数据28，所以只能使用顺序查找B.使用二分查找数据时，第1次查找的数据是d[3]C.使用二分查找任何查找键时，查找的次数最少3次D.使用二分查找数据时，第2次查找的数据可能是d[1]或d[6]14.数组P中存放着学生的相关信息，如图所示，若要查找数组中是否存在“小李”的信息，以下说法正确的是()P(1)P(2)P(3)P(4)P(5)P(6)P(7)P(8)P(9)P(10)小张小李小杨小陈小郑小王小邓小周小郭小范A.在数组P中既能使用顺序查找也能使用二分查找B.在数组P中使用顺序查找需要查找2次C.在数组P中使用二分查找需要查找4次D.在数组P中二分查找的效率高于顺序查找15.分别使用顺序查找算法和二分查找算法在数据序列“5,6,10,13,15,20,21,26,30”中查找数据10,下列关于查找的次数的说法中正确的是（）A.顺序查找2次,二分查找3次B.顺序查找3次,二分查找2次C.顺序查找3次,二分查找3次D.顺序查找3次,二分查找4次参考答案：1.答案：C[解析]利用对分查找的原理可以，第一次访问5位置的55，55<93，所以第二次访问81，82<93，第三次访问93，故选:C.2.答案：B[解析]顺序查找是比数据的第一个元素开始依次比较，AC两项分别查找53和70的次数为5次和8次，说法正确;B项对分查找53，i=1，j=12，m=(i+j)2=6，第6个元素为55，比53大，因此i=1，j=m1=5，m=(i+j)\2=3，第3个元素为41,41比53小，i=m+1=4，j=5，m=(i+j)\2=4,第4个元素为43，43比53小，因此，i=m+1=5，j=5，m=(i+j)\2=5，第5个元素为53，找到元素，共查找了4次，而非3次;故选:B.3.答案：C[解析]本题考查顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素,因此使用顺序查找时,共查找3次。使用二分查找时,依次被访问的数据为15，6,10,即二分查找的次数也为3。4.答案：C[解析]从10个数“21,45,56,65,68,72,79,83,88,96"中查找75的二叉判定树如图所示,故答案选C。5.答案：[解析]该二分查找用二叉树表示如下，结合选项，可知依次需要进行比较的数据可能是4。故选A。6.答案：D[解析]顺序查找对被查找的数据是否有序没有要求而对分查找时被查找的数据必须有序。故A、B选项错误。顺序查找和对分查找都不能保证一定能找到要查找的关键字，C选项错误。顺序查找是对全部范围内的每个元素依次进行比较，而对分查找每次对一半范围内的数据进行比较，一般来说，对分查找的效率比顺序查找要高，D选项正确。故选