第18课 数据查找1——查找算法基础-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第18课　数据查找1——查找算法基础(见学生用书P114) ——5.4　数据查找，教材P147～158 1.理解查找的概念和基本方法。　2.理解顺序查找的思想，能利用顺序查找算法设计程序解决实际问题。　3.理解二分查找的思想，能利用二分查找算法设计程序解决实际问题 。 查找(Search)又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象值本身。 1．顺序查找 (1)顺序查找(Sequential Search)又称线性查找，从顺序表的　一端　开始，　依次　将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的关键字等于key，则表明查找　成功　；若所有元素都比较完毕仍找不到，则表明查找　失败　。 　　　　　　　　　　　　　　　顺序查找过程实例 (2)顺序查找的特点 ①顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其算法简单，时间复杂度为　O(n)　。 ②对存放数据的表结构无任何要求，不管数据　是否有序　，均可适用。 ③顺序查找算法的平均比较次数为：(n＋1)/2。 (3)顺序查找算法实现 ①在规模为n的数组d 中进行顺序查找的流程图如下所示： 　　　　　　　　　　　　　顺序查找算法流程图 ②程序代码： 程序代码1 程序代码2 d＝[25，22，13，18，14，11，17，19] key＝int(input(”输入需要查找的数：　”)) flag＝False n＝len(d) for i in range(n)： if d[i]＝＝key： flag＝True break if flag＝＝True： print(”查找成功！　”) else： print(”未找到！　”) def seq_search(s，a)： n＝len(s) flag＝False n＝len(d) for i in range(n)： if d[i]＝＝key： flag＝True break if flag＝＝True： return ”查找成功！　” else： return ”未找到！　” d＝[25，22，13，18，14，11，17，19] key＝int(input(”输入需要查找的数：　”)) result＝seq_search(d，key) print(result) ③运行结果： 输入需要查找的数：　18 查找成功！ 输入需要查找的数：　20 未找到！ 2．二分查找 (1)二分查找(Binary Search)又称折半查找、对分查找。它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。 (2)二分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素的数值与查找键不同，根据数组元素的有序性，就可确定在数组的前半部分还是后半部分继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 二分查找的算法时间复杂度为O(log2n)。二分查找的前提是数据有序，对n个数据查找，最多查找次数为int(log2n)＋1。 (3)查找过程 若key为查找关键字，数组d存放n个已按升序排序的数据。使用二分查找时，把查找范围(i，j)的中间位置上的数据d[m]与key进行比较，结果必然是以下三种情况之一： ①key<d[m]，查找键小于中点d[m]处的数据。由数组d 中的数据递增性可以确定：在(m，j)内不可能存在值为key的数据，必须在新的范围(i，m－1)中继续查找。 ②key＝d[m]，找到了需要的数据。 ③key>d[m]，查找键大于中点d[m]处的数据。由数组d 中的数据递减性可以确定：在(i，m)内不可能存在值为key的数据，必须在新的范围(m＋1，j)中继续查找。 以数组d 为例，观察二分查找的过程。若要查找的数据key＝12，则查找过程如图所示： 　　　　　　　　　　　　　二分查找过程实例 (4)二分查找算法实现 ①在规模为n的数组d 中进行二分查找的流程图如下所示： 　　　　　　　　　　　　　　　二分查找算法流程图 ②程序代码： 程序代码1 程序代码2(递归) key＝int(input(”输入需要查找的数：　”)) d＝[6，12，15，18，22，25，28，35，46，58，60] f＝False i＝0 j＝len(d)－1 while i<＝j： m＝(i＋j)//2 if d[m]＝＝key： f＝True b＝m break if key<d[m]： j＝m－1 else： i＝m＋1 if f＝＝True： print(”查找成功！　”) else： print(”没有找到！　”) def bsearch(s，a)： if len(a)＝＝0： print(”没有找到！　”) return False m＝len(a)//2 if d[m]＝＝s： print(”查找成功！　”) return True if s<a[m]： return bsearch(s，a[：m]) else： return bsearch(s，a[m＋1：]) key＝int(input(”输入需要查找的数：　”)) d＝[6，12，15，18，22，25，28，35，46，58，60] bsearch(key，d) ③运行结果： 输入需要查找的数：　12 查找成功！ 输入需要查找的数：　61 没有找到！ (5)二分查找的判定树 ①二分查找过程可用一棵二叉树来描述，树中的每个根节点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表。 　　　　　　　　　　　　　　　二分查找的判定树实例 ②查找12时，从根节点到待查节点的一条路径为25→15→6→12，查找次数为4次。 ③由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。 1． 二叉排序树 二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。 (1)排序 ①二叉排序树的排序功能主要通过二叉树的建立和遍历过程来实现，其在建立过程中要始终满足如下性质： 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。 它的左右子树也分别为二叉排序树。 ②构建 现有序列：a＝[61，87，59，47，35，73，51，98，37，93] 索引 i＝0，a[i]＝61，节点61作为根节点。 索引 i＝1，a[i]＝87，87>61，且节点61的右孩子为空，故87为61节点的右孩子。 索引 i＝2，a[i]＝59，59<61，且节点61的左孩子为空，故59为61节点的左孩子。 索引 i＝3，a[i]＝47，47<59，且节点59的左孩子为空，故47为59节点的左孩子。 　　采用同样规则遍历整个数组得到一棵二叉排序树。 　　　　　　　　　　　　　　　二叉排序树 遍历打印可以使用中序遍历，打印出来的结果是从小到大的有序数组。 (2)查找 如果树是空的，则查找结束，无匹配。 如果被查找的值和根节点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根节点的值就选择左子树，大于根节点的值就选择右子树。 2． 二分查找的相关变形 对分边界查找四种变式对比及规律总结 循环条件 L<＝R L<R L<R L＋1<R L、R初值 L，R＝0，n－1 L，R ＝－1，n－1 L，R＝0，n L，R＝－1，n 循环结束L、R关系 R＋1＝L L＝R L＝R L＋1＝R 查找区间 [L，R] (L，R] [L，R) (L，R) 中点m取值 (L＋R)//2 (L＋R ＋ 1)//2 (L＋R＋1)//2 (L＋R)//2 (L＋R)//2 (L＋R＋ 1)//2 左偏 右偏 形右实左 形左实右 左偏 右偏 循环结束后，中点m是不确定的，不能根据m的值确定边界！ 二叉树形态 (4个元素为例) 右偏 左偏 右偏 左偏 右偏 左偏 区 域 二 分 精 准 定 位 理解图形 L 代码 if a[m]<＝key： 　L＝m＋1 else： R＝m－1 if a[m]<＝key： 　L＝m else： R＝m－1 if a[m]<＝key： 　L＝m＋1 else： R＝m if a[m]<＝key： 　L＝m else： R＝m 返回值 R或L－1 R或L R－1或L－1 L或R－1 R 代码 if a[m]>key： 　R＝m－1 else： L＝m＋1 if a[m]>key： 　R＝m－1 else： L＝m if a[m]>key： 　R＝m－1 else： L＝m＋1 if a[m]>key： 　R＝m－1 else： L＝m 数组a元素是不下降序列，相邻元素满足： a[i]<＝a[i＋1]， 变量： n＝len(a) 查找小于等于key的最大数位置(索引)，习惯称查找右边界 　　下列关于查找的说法中，不正确的是(　C　) A．采用顺序查找时，被查找的数据集中的元素无需有序 B．采用二分查找时，被查找的数据集中的元素必须有序 C．二分查找总能找到要查的键值 D．二分查找的效率通常比顺序查找要高 【解析】 顺序查找对被查找的数据是否有序没有要求，而二分查找要求被查找的数据必须有序。顺序查找和二分查找都不能保证一定能找到要查找的关键字，选项C错误。 变式1要从n个数据元素中顺序查找某个元素是否存在，最多查找次数是(　C　) A．1　　　　　　B．n/2　　　　　　C．n　　　　　　D．(n＋1)/2 【解析】 根据顺序查找思想，将给定的值与原数据进行逐个比较。若要找的数刚好是第一个，则查找次数为1；若要找的数为最后一个(或找不到) ，则查找次数为n，也是最多的查找次数。故选项C正确。 变式2某活动中有一个猜价格的游戏，对一件价格为2000元以内的物品进行竞猜，如下是一种猜价格的方案：第1次猜1000元；若高了，则第2次猜500元；若低了，则第3次猜750元，直至猜对。若某件物品的价格为625元，则此价格被猜中至少需要的次数是(　A　) A．4次 B．3次 C．2次 D．1次 【解析】 题目要求算二分查找中比较的次数。开始时，有序查找的范围是1～2000，查找键是625。第1次猜的值为1000，由于1000大于查找键，于是新查找范围为1～999；第2次猜的值为500，小于查找键，于是新查找范围为501～999；第3次猜的值为750，大于查找键，于是新的查找范围为501～749；第4次猜的是中间值，为625，查找成功，故猜的次数至少为4。故选项A正确。 　　有如下Python 程序段： a＝[1，2，3，－7，4，－2，6，8] s，ans＝a[0]，a[0] for i in range(1，len(a))： if s＋a[i]>a[i]： 　s＋＝a[i] else： s＝a[i] if s>ans： ans＝s 执行该程序段后，ans 的值为(　C　) A．14 B．15 C．16 D．17 【解析】 执行过程为： i 1 2 3 4 5 6 7 a[i] 1 2 3 －7 4 －2 6 8 s 1 3 6 －1 4 2 8 16 ans 1 3 6 6 6 6 8 16 选项C正确。 变式1从若干个整数中找到最大值并输出。有如下Python 程序段，横线处填入的代码应为(　C　) a＝[44，23，53，34，22，1，56，345，45，53] n＝len(a) maxx＝a[0] for i in range(1，n)： if a[i]>maxx： 　　　　　　 # print(maxx) A．a[i]＝maxx B．maxx＝i C．maxx＝a[i] D．maxx＝a[1] 【解析】 利用maxx记下最大值，i是元素位置，a[i]是值，选项C正确。 　　某二分查找算法的Python 程序段如下： i＝0；j＝7；n＝0 while i<＝j： n＝n＋1 m＝(i＋j)//2 if key＝＝d[m]： break elif key>d[m]： j＝m－1 else： i＝m＋1 数组元素d[0]到d[7]的值依次为“83，75，62，41，33，27，16，2”，执行该程序段后，若n的值为2，则key的值可能是(　C　) A．62或16 B．62或27 C．75或27 D．75或16 【解析】 程序实现的是二分查找的过程，每次查找中间位置的数据，第一次查找的数据41，第二次可能往前半部分查找75，或者往后半部分查找27，n的值为2，说明查找次数是2次，因此key可能的值为75或27。 变式1有如下Python 程序段： a＝[0，20，23，23，24，24，31，48，49，73，75] key＝int(input()) c＝0 i，j＝1，10 while i<＝j： m＝(i＋j)//2 if a[m]<＝key： 　i＝m＋1 else： j＝m－1 c＋＝1 print(c) 执行该程序段后，若输出的结果是3，则输入的key 可能是(　B　) A．20 或73 B．24 或49 C．23 或24 D．23 或49 【解析】 注意点是原始查找范围是闭区间[1，10]而不是[0，10]，同时当找到key 的值时仍要往右边查找，结合二分查找判定树如下，当key＝20、24、49 时，查找的次数是3，当key＝23、31、73 时，查找的次数是4。故选项B正确。 变式2某对分查找算法的Python程序段如下： left＝0；right＝7；s＝”” d＝[14，23，29，34，38，42，52，69] key＝int(input('请输入要查找的数据')) while left<＝right： mid＝(left＋right)//2 if key＝＝d[mid]： 　s＝s＋”M” if key<＝d[mid]： 　right＝mid－1；s＝s＋”L” else： left＝mid＋1；s＝s＋”R” 执行该程序段后，显示的内容可能是(　A　) A．RRRML B．LM C．LMRL D．LRRM 【解析】 由题可知，当key＝d[mid]时，循环不跳出。因此，该查找过程会一直进行，直到循环条件不满足结束。可以借助二叉判定树来表示查找的路径和过程，如下图所示(当key＝d[mid]时，也满足key<＝d[mid]的条件，因此s在右侧拼上M和L)，只有选项A满足条件。 变式3有如下Python 程序段： import random def find(x，y)： m＝(x＋y＋1)//2 if a[m]＝＝key： return m if a[m]>key： y＝m－1 else： x＝m＋1 return find (x，y) a＝[2，4，6，8，10，12，14，16] key＝random.choice(a) #从序列的元素中随机挑选一个元素 i＝0；j＝len(a)－1 xb＝find(i，j) print(xb，key) 执行该程序段后，函数find()被调用的次数最多是(　B　) A．3 B．4 C．5 D．6 【解析】 由“key＝random.choice(a)”可知查找键key 是一定可以找得到的，由题中算法可知，最少需要找1 次，最多需要找int(log2n)＋1 次，本题中序列a 中共有8 个元素，则最多找4 次。 变式42023·湖州中学检测有如下Python 程序段： import random a＝[15，18，25，34，38，40，55，61，80，85] key＝random.randint(15，55) f＝[0]*10；i＝0 j＝len(a)－1 while i<＝j： m＝(i＋j＋1)//2 if a[m]>key： 　j＝m－1 else： if a[m]%5＝＝0： f[m]＝1 i＝m＋1 执行该程序段后，列表f 的值可能是(　D　) A．[0，0，1，0，0，1，0，0，0，0] B．[0，0，0，0，0，1，0，0，1，0] C．[1，0，1，0，0，0，0，0，0，0] D．[0，0，0，0，0，1，1，0，0，0] 【解析】 这题的关键，f[m]＝1 赋值语句的执行条件为a[m]<＝key and a[m]%5＝＝0，此时抛弃左半区域，在右半区域[m＋1，j]继续查找。选项A，如果f[5]＝1，那么f[2]不可能为1，选项错误；选项B，f[5]＝1，根据key 的范围，f[8]>key 一定成立，所以，f[8]不会赋值为1，选项错误；选项C，f[5]>key，接下来f[2]<＝key，f[2]赋值1，f[0]不可能为1，选项错误；选项D，f[5]＝1，接下来中点下标依次是8，7，6，f[6]＝＝55，满足条件，选项正确。 　　如下Python程序实现的功能是：在非降序的数组a中查找小于等于key的元素的最大下标值。 #读取一批非降序的数据保存在数组a中，代码略 key＝int(input(”请输入待查找的数据：　”)) i，j＝0，len(a)－1 while i<j： m＝(i＋j＋1)//2 if 　　　　　　： 　　　　j＝m－1 else： i＝m print(i) 则横线处填入的代码应为 (　D　) A．a[m]<＝key B．a[m]<key C．a[m]>＝key D．a[m]>key 【解析】 查找小于等于key的元素的最大下标值，意味着在非降序数组a中，若a[m]<＝key，应该在m的右侧查找，即调整i的值，即会执行else分支，故①处条件不应包含等于。 变式1下面Python 程序用于产生n 个[10，50]范围内的随机整数，并按从小到大的顺序输出其中不大于Key 值的整数： from random import * n＝20 a＝[randint(10，50) for i in range(n)] a．sort()#对随机数组a 进行升序排序 i＝0 ①　　　　　　　 key＝int(input(”请输入Key：　”)) while i<j： ②　　　　　　　 if a[m]>key： j＝m else： i＝m＋1 print(”原数组升序后为：　”，a) print(”Key＝”，key) print(”数组中不大于Key 的整数为：　”，③　　　　　) 上述程序段中①、②和③填入的代码应为(　A　) A．①j＝n　②m＝(i＋j)//2　③a[：i] B．①j＝n　②m＝(i＋j＋1)//2　③a[：m] C．①j＝n－1　②m＝(i＋j＋1)//2　③a[：m] D．①j＝n－1　②m＝(i＋j)//2　③a[：i] 【解析】 数组a 为升序，需要求的为不大于key 的整数即找到第一个大于等于key 的位置。根据while 的条件为i<j，故初始j 的范围应为n(j＝n 取不到)，因为j 是取不到的索引故m 的取值只能是左偏，不然会越界(例如i＝n－1，j＝n 的时候，如果用m＝(i＋j＋1)//2，得到索引为n，越界。m＝(i＋j)//2，得到索引为n－1)。二分查找的位置结果存储在i 中，故选项A正确。 |随|堂|检|测| 1． 给定任意的查找键，在序列3，5，8，12，15，23中进行查找，下列说法不正确的是(　D　) A．若用顺序查找实现，则最少查找1次 B．若用二分查找实现，则最少查找1次 C．若用顺序查找实现，则最多查找6次 D．若用二分查找实现，则最多查找4次 【解析】 顺序查找和对分查找都有1次查找成功的情况，顺序查找次数的最多情况是从前往后找到最后的数据，二分查找每次查找范围中间位置的数据，6个数据最多查找3次，选项D错误。 2．有如下Python程序段： a＝[9，1，7，3，8，4] key＝5 pmin＝a[0] for i in range(1，len(a))： if key<a[i]<pmin： pmin＝a[i] print(pmin) 执行该程序段后，输出的结果是(　C　) A．1 B．4 C．7 D．9 【解析】 程序功能为在列表a中顺序查找比key大的最小值，选项C正确。 3．2023·长兴中学检测某算法的Python程序段如下： key＝randint(0，3)*2＋13 i，j，c＝0，len(a)－1，0 while i<＝j ： m＝(i＋j＋1)//2 if a[m]>＝key： 　i＝m＋1 else： j＝m－1 c＋＝1 列表a＝[23，21，19，18，16，15，14，11]，执行该程序段后，下列说法不正确的是(　B　) A．i 的值为j＋1 B．i 的值可能是8 C．j 的值可能是5 D．c 的值一定是3 【解析】 key 的值有四种可能：13，15，17，19，画出二分查找树，注意找到后不退出。当key＝13，未找到，最终i＝7，j＝6；当key＝15，第三次找到，但是还是会往后继续找，最终i＝6，j＝5；当key＝17，未找到，最终i＝4，j＝3；当key＝19，第二次就找到，但是还是会往后继续找，最终i＝3，j＝2；选项A， i＝j＋1，选项正确；选项B，观察key 的四种可能，i 不可能等于8，选项错误；选项C， 当key＝15 时，i＝6，j＝5，选项正确；选项D，c 为查找次数，因为该程序找到后不退出，所以会继续往后找，因为key 小于23，不会往最左边那条路径，故不可能查找4 次，故c 一定等于3，选项正确。 4．有如下Python程序段： a＝[4，9，12，34，49，55] f＝[0，0，0，0，0，0] for i in range(6)： key＝int(input()) L＝0；R＝5；c＝0 while L<＝R： m＝(L＋R)//2；c＝c＋1 if a[m]＝＝key： 　f[i]＝c；break elif a[m]>key： 　　　R＝m－1 else： L＝m＋1 执行该程序段后，若输入任意的key值，则列表f的值不可能是(　B　) A．[0，0，0，0，0，0] B．[2，0，2，0，2，0] C．[2，3，0，0，2，3] D．[2，3，1，3，2，3] 【解析】 有两个循环，内循环是对分查找，变量c表示查找次数，外循环i表示进行了6次循环，每次输入一个key，在列表a中查找是否能够找到，查找次数记录在列表f中，f[i]表示第i趟的查找次数，结合6个数的二叉树(如图所示)，若能找到，则f[0]＝2，f[1]＝3，f[2]＝1，f[3]＝3，f[4]＝2，f[5]＝3，若找不到则值为0，则选项B中f[2]不可能为2，只能为1或0。 5． 下列Python 程序段功能为：在非降序排序列表L 中，采用二分查找的方式查找某数值。若能找到，则输出该数值在列表L 中的起始和结束位置，否则输出“未找到”。 key＝int(input(”key＝”)) i＝0；j＝9 while i<＝j： m＝(i＋j)//2 if①　　　　　　： 　j＝m－1 else： i＝m＋1 if L[j]！＝key： print(”未找到”) else： s1＝j while key＝＝L[j]and j>＝1： j＝j－1 ②　　　　　　 print(str(s2)，”－”，str(s1)) 上述程序段中横线处填入的代码应为(　B　) A．①key<L[m]　②s2＝j B．①key<L[m]　②s2＝j＋1 C．①key<＝L[m]　②s2＝j D．①key<＝L[m]　②s2＝j 【解析】 由代码“s1＝j” 可知j 为结束位置索引，故前半部分程序要实现的功能为：如果该数值在列表L 中多次出现，用j 记录该数值最后一次出现的位置。该查找算法找到后不退出，继续往后比较，查找是否有相同的数再次出现，必须有代码key>＝L[m]，i＝m＋1，做到如果key 与L[m]相同，会继续往后找，直到j 记录下该数值在列表L最后一次出现的位置。故第一空答案为key<L[m]。由输出可知s2 为起始索引，第二部分程序是通过循环查找该数值在列表L 中的起始索引，由“while key＝＝L[j]and j>＝1：”可知，这是从后往前找的过程，但是注意，如果本次往前找时找到了相同数值，但是前一个不相同，出循环的时候执行了j＝j－1，下一次循环就进不去了。所以，此时j 的后一个才是起始索引，故第二空答案为s2＝j＋1，选项B正确。 学科网（北京）股份有限公司 $$