第19课 数据查找2——二分查找应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第19课　数据查找2——二分查找应用(见学生用书P154) ——5.4　数据查找，教材P147～158 理解二分查找的思想，能利用二分查找算法设计程序来解决实际问题。 在计算机应用中，查找是常用的基本运算，一般先通过查找算法找到某个对象，然后对其进行相应操作。 　　输入n 个数据按降序依次存储在数组元素a[0]，a[l]，a[2]，…，a[n－1]中，从中查找键值key，代码实现如下： #将n 个降序的数据读入数组元素a[0]至a[n－1]，代码略 key＝int(input(”输入需要查找的数：　”)) i＝0 j＝n－1 flag＝False while ①　i<＝j and not flag 或 i<＝j and flag＝＝False　： m＝(i＋j)//2 if a[m]＝＝key： flag＝True ans＝m eli f②　key>a[m] 或 a[m]<key　： 　　j＝m－1 else： ③　i＝m＋l　 if flag： print(”查找成功！该元素在数组a[”＋str(ans)＋”]中”) else： print(”没有找到！　”) 【解析】 由题意可知数组元素已经降序排序，查找区间[i，j]，是否查找成功标记flag，若未找完且未找到，则继续查找，所以①处填“ i<＝j and not flag” 或“i<＝j and flag＝＝False ”；由于元素是降序的，由j＝m－1 可知，下一次查找是在原来区间的左半边，故②处的条件应该是“key>a[m]”；根据二分查找算法思想，③处则该填写“i＝m＋1”。 变式1插补查找算法又称为插值查找，它是二分查找算法的改进版。插补查找是按照数据的分布，利用公式预测键值所在的位置，快速缩小键值所在序列的范围，慢慢逼近，直到查找到数据为止。它类似于平常查字典的方法。例如，我们在翻字典查一个发音以字母B开头的文字时，不会使用二分查找法找字典的中间部分，因为根据字典的顺序可知，发音以B开头的文字应该在字典较前的部分，所以可以从字典前部的某处开始查找。插补查找算法的所谓中间位置键值索引计算方式： middle＝low＋(target－data[low])/(data[high]－data[low])*(high－low) 参数说明： data：数据列表；middle：当前需要比对的数据索引；low：最左侧数据的索引；high：最右侧数据的索引；target：查找的目标数据。 现有150名学生(编号从1到150)参加军训拉练，从中随机选取9名同学作为旗手，如[[12，'薛丁']，[45，'李强']，[56，'徐梓']，[66，'鲍杰']，[77，'黄怡']，[80，'余澍']，[97，'金维']，[101，'方茹']，[120，'陈昀']]。现在某位家长想知道方茹同学是否被选到，如果被选到，她是第几名旗手。为了解决这个问题，可以使用插补查找算法来解决问题。例如，查找方茹，需要输入101进行查找，具体如下图所示： 请回答下列问题。 (1)在题目所示案例中，若使用插补查找算法查找45，则该过程中访问到的数据编号依次为　56、45　。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 def search(data，num)：#定义查找函数，参数是原数列data和键值num low＝0 #定义变量用来表示低位 high＝len(data)－1 #定义变量用来表示高位 print(”正在查找……”)#提示 while low<＝high and num！＝－1： left＝data[low][0] mid＝low＋(num－left)*(high－low)①　//(data[high][0]－data[low][0]) 或 //(data[high][0]－left)　 print(f”正在查看第{mid＋1}个旗手[{data[mid]}]”) if num<data[mid][0]： 　high＝mid－1 elif num>data[mid][0]： low＝mid＋1 else： ②　return mid　 return －1 num＝0 #定义变量，用来输入键值 students＝[[12，'薛丁']，[45，'李强']，[56，'徐梓']，[66，'鲍杰']，[77，'黄怡']，[80，'余澍']，[97，'金维']，[101，'方茹']，[120，'陈昀']] #定义旗手列表 print(”旗手如下：　”) for i in range(len(students))： print(f'(编号：　{students[i][0]})[{students[i][1]}]'，end＝' ') #输出数列 print('') number＝0 #定义变量用来存储查找结果 num＝int(input(”请输入需要查找的学生编号：　”)) #输入查找键值 ③　number＝search(students，num) 或 number＋＝search(students，num)　 if number＝＝－1：#判断查找结果是否是－1 print(f'没有找到编号为[{num}]的学生') else： print(f'{students[number][1]}同学是第{number＋1}个旗手') 【解析】 (1)初始状态：low＝0， high＝8， mid＝0＋(45－12)*8 // (120－12)＝2， 访问到56 号，未找到45号，low更新为：low＝0 high＝1 mid＝0＋(45－12)*1 // (45－12)＝1，查找45 号找到数据后结束程序。故答案为：56、45。 (2)①第①空的大致思路与第(1)题一致，即在题干描述基础上模拟变量即可。此处的变量num 即题干中的target，变量left 即题干中的data[low]等等，以此类比。值得注意的是变量mid 作为data 列表的索引，必须为整数，而本题中又没有int()取整操作，所以在除以data[high][0]－left 时需要使用整除运算符“//”，故答案为“//(data[high][0]－left )”。 ②第②空较为简单，if——elif 语句块中，排除了两种未找到情况，只剩下恰好找到num 数据的情况。所以此时结束函数，将num 的位置mid 作为函数值带回即可，答案为“return mid”。 ③第③空在主程序中调用函数，注意参数的含义与位置，num 为待查找编号，学生数据存放在列表students中，最后用变量number 来输出找到的学生数据，且number 是students 的索引。借此建立函数、参数、函数值的对应关系：number＝search(students， num)。 　　将并列一排的n 个房间(房间间距均为1 个单位)依次编号为1～n，其中k 个房间需要配送服务，现有处于不同房间的m 台机器人可提供配送服务。配送系统为管理方便，对所有机器人设置相同的配送半径r(机器人以所在房间为起点，可配送左右各r 个连续房间)。可以设置最小配送半径来满足k 个房间的配送要求。 例如，根据系统依次采集到的数据，当前需要配送的5 个房间编号分别为1，8，3，4，7，可提供配送服务的机器人1、机器人2 分别在房间2、房间7处，如下图所示。各房间可选择最近的机器人提供配送服务，例如房间4 离机器人1 的距离为2，离机器人2 的距离为3，因此可以选择机器人1 提供配送服务。确定各房间所选择的机器人后，计算各房间与所选择的机器人的距离，取其最大值即为最小配送半径。因此，要满足这5 个房间的配送要求，2 台机器人的最小配送半径可以设置为2。 (1)若需配送服务的房间编号分别为1，3，2，4，5，6，可提供配送服务的2 台机器人所处房间编号为4，1，则最小配送半径应设置为　2　。 (2)计算机器人最小配送半径的Python 程序如下，请在横线处填入合适的代码。 def sort_arr(a)： #对数组进行升序排序 m＝len(a) i＝1 ①　flag＝True　 while i<＝m－1 and flag＝＝True： flag＝False for j in ②　range(m－1，i－1，－1) 或range(1，m－i＋1，1) 或其他等价答案　： if a[j]<a[j－1]： a[j]，a[j－1]＝a[j－1]，a[j] flag＝True i＋＝1 return a def bisearch(v，b)： i，k＝0，len(b) j＝k－1 while i<＝j： mid＝(i＋j)//2 if ③　b[mid]<v 或b[mid]<＝v 或其他等价答案　： 　　　i＝mid＋1 else： j＝mid－1 return i def max_min(houses，b)： minr＝0 for h in houses： R＝bisearch(h， b) if R＝＝len(b)： r＝h－b[R－1] elif R＝＝0： r＝b[R]－h else： ④　r＝min(b[R]－h，h－b[R－1]) 或其他等价答案　 minr＝max(r，minr) return minr if 　name　＝＝'　main　'： #主程序 #将需要配送服务的房间编号存入整型数组houses #将机器人所在房间编号存入整型数组b，代码略 #例如：houses＝[8，3，4，7，1]，b＝[7，3] b＝sort_arr(b) print(max_min (houses，b)) #输出最小配送半径 【解析】 (1)根据题意分析，房间1、4 有机器人，编号为1～6 的房间需要服务时，1、4 房间的机器人均可以在半径2 以内服务，答案为2。 (2)程序代码第一个函数sort_arr()的功能是对数组进行升序排序。本题中的排序是一种对冒泡的优化，通过flag 变量标记当前第i 遍排序中是否发生交换来控制循环。若无交换则说明剩余待排元素已经有序，可以提前结束算法。所以第①空初始化标记即可。第②空是对升序待排序列元素的访问，冒泡排序算法并未规定内循环的遍历方向，但是观察已有变量i 的初值与更新方式会发现，在本题中使用倒序遍历的写法更为方便。随着i 的增加，前端元素逐渐有序，对于第i 遍排序，待排元素的区间为[i－1，m－1]，由元素比较规则“if a[j]<a[j－1]：”可知第②空答案为range(m－1，i－1，－1)。也可以使用正序遍历的方式让后端元素先有序，答案为raneg(1，m－i＋1)。本题中说明了在不同房间中有机器人，即列表b 中是没有重复元素的，此时对于它的对分不必考虑重复元素的取值方向问题，因此第③空答案为b[mid]<v 或b[mid]<＝v 均可。程序代码第二个函数bisearch()是对分查找，对于参数v、b 需要结合后面的max_min()函数和主程序一起思考。主程序调用max_min()函数用于计算最小半径，其中house 和b 分别表示待服务房间列表和有机器人的房间列表(已升序)。而在max_min()中调用的bisearch()函数，其参数h和b 分别表示当前房间号和有机器人的房间列表。根据其变量R 的更新推测，bisearch()函数用于计算“编号大于h 房间的最近有机器人的房间编号”。因此第④空答案为r＝min(b[R]－h，h－b[R－1])。 |随|堂|检|测| 2023·玉环中学检测某公司计划采购一批商品，供货清单保存在文件“sell.csv”(如图1)中，采购清单保存在文件“buy.csv”(如图2)中，现需要计算购买商品所需的最少总花费。 采购规则： ①同一商品按价格从低到高购买。 ②若某商品供货充足，则按采购量购买；若供货不足，则采购所有供货数量。 (1)商品查找时采用的算法是 　B　(单选：A.顺序查找/B.二分查找)，这种算法的时间复杂度为　B　(单选： A．O(n)/B.O(log2n)/C.O(n2))。 (2)请在横线处填入合适的代码。 #从文件中读取供货清单保存在列表sell中，读取采购清单到列表buy中。保存格式为： #sell＝[['1001'，10，10]，['1002'，80，5]，…] sell＝[['1001'，10，10]，['1002'，80，5]，…] #sell中的商品以商品名称为主关键字，商品价格为次关键字升序排序，实现代码略 def bsearch(sp，i，j)： #查找商品sp在供货清单(排序后)中第一次出现的位置 pos＝－1 while i<＝j： m＝(i＋j)//2 if sell[m][0]＝＝sp： pos＝m；j＝m－1 elif ①　sell[m][0]>sp　： j＝m－1 else： i＝m＋1 return pos tot＝0 print(”商品名称”，”购买数量”，”价格”，”费用”) for i in range(1，len(buy))： sp＝buy[i][0] pos＝bsearch(sp，1，len(sell)－1) if pos＝＝－1： print(sp，”none”，”none”，0) else： while pos<len(sell) and ②　sell[pos][0]＝＝sp　： if sell[pos][1]>＝buy[i][1]： #第 i件商品按采购量购买 fy＝buy[i][1]*sell[pos][2] print(sp，buy[i][1]，sell[pos][2]，fy) buy[i][1]＝0 tot＋＝fy break else： ③　fy＝sell[pos][1]*sell[pos][2]　 print(sp，sell[pos][1]，sell[pos][2]，fy) buy[i][1]－＝sell[pos][1] pos＋＝1 tot＋＝fy print(”购买商品所需的总费用最少为”＋str(tot)＋”元”) 【解析】 (1)函数为二分查找，时间复杂度为O(log2n)。 (2)二维列表buy(购买)的存储结构为[[”1001”，55]，[”1002”，200]，[”1003”，50]，[”1004”，100]]；遍历购买列表，查找商品在供货清单(排序后)中第一次出现的位置，调用函数bsearch实现这一功能；由于是升序排序，根据j＝m－1得知，中点值应大于查找值，答案为sell[m][0]>sp，函数返回位置给变量pos，如果pos不为－1，则从pos位置开始遍历清单列表，进行购买，若if条件成立，则第 i件商品按采购量购买，如果不成立，则将供货清单中该产品全部买下，计算剩余购买数量及目前总价，并将pos后移，继续采购同一种产品，②处是判断pos的下一位，是否为同一商品，答案为sell[pos][0]＝＝sp；③计算费用，答案为fy＝sell[pos][1]*sell[pos][2]。 学科网（北京）股份有限公司 $$