高中信息技术浙教版（2019）选修1 第五章　课时5　二分查找（学案 课件，2份打包）

(课件网) 课时5　二分查找 第五章　数据结构与算法 1.通过实例分析，理解顺序查找的基本思想，掌握使用二分查找的一般方法。 2.能根据不同的应用场景，选择合适的数据结构，能灵活使用二分查找算法编写程序。 目 录 CONTENTS 知识梳理 01 例题精析 02 随堂检测 03 巩固与提升 04 知识梳理 1 1.二分查找(Binary Search) 二分查找又称对分查找或折半查找。 二分查找是指在有序的数据序列中，首先将要查找的数据元素与数组的_____元素进行比较，如果相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定新的_____(在数组的前半部分还是在后半部分)；在确定了新的查找范围后，重复进行以上操作，直到找到或查找结束为止。 ①二分查找的前提条件是待查找的数据序列必须有序。 ②“未找到”是指当前查找区间不存在，即区间左端点大于右端点。 中间位置 查找范围 2.二分查找的算法框架 说明：要查找的目标数据元素为key，待查找的数据元素存放在数组d中。 i、j分别为查找区间的起点位置和终点位置，m为查找区间的中间位置，n为数据元素个数。 i＝0 j＝n－1 while i<＝j： #计算中点位置m #比较key与d[m]，并做相应处理 #若i>j，则表示未找到 3.二分查找的程序实现 ·设要查找的数据是key，待查找的数据元素存放在数组d中，并已按升序排序。 ·输出查找结果，若找到则输出信息“找到！位置为：X”，否则输出“查无此数！” ·输出查找次数c。 二分查找主要代码如下(以升序为例)： 输入key的值 c＝0　　　　　　　#记录查找次数 find＝False　　　　#设置find的初值 i＝0　　　　　　　#区间左端点位置 j＝n－1　　　　　 #区间右端点位置 while _____：　#还未找完并且还未找到，则继续查找 c＝c＋1　　　　#查找次数记数 m＝_____　 #计算中点位置m，等价于m＝int((i＋j)/2) if key＝＝d[m]：　 #找到目标元素，并进行相应处理 find＝True print(m) if key>d[m]：　　#表示要查找的元素比中间位置上的元素大时 i＝m＋1　　　#调整区间左端点 i<＝j and not find (i＋j)∥2 else：　　　　　 j＝m－1　　　#调整区间右端点 if find＝＝False： print(″查无此数！″) print(″查找次数为：″，c) 例题精析 2 例1 有如下两组数据： A ①1，2，3，4，5，6，7，8，9 ②3，4，5，2，1，8，7，6，9 A.①②都可以直接使用二分查找 B.①②都可以直接使用顺序查找 C.①可以直接使用顺序查找，也可以直接使用二分查找 D.②可以直接使用顺序查找，但不能直接使用二分查找 解析　本题主要考查的是使用顺序查找和对分查找的适用条件。顺序查找对待查找的数据没有要求，而二分查找的前提是数据必须有序。①中数据有序，②中数据无序，①中数据顺序查找和二分查找均可以直接使用，②中数据只能使用顺序查找，若要使用二分查找，则先对②中数据进行排序操作。因此，不正确的是A，答案为A。 变式训练　分别使用顺序查找算法和二分查找算法在数据序列“5，6，10，13，15，20，21，26，30”中查找数据10，下列关于查找的次数的说法中正确的是(　　) A.顺序查找2次，二分查找3次 B.顺序查找3次，二分查找2次 C.顺序查找3次，二分查找3次 D.顺序查找3次，二分查找4次 解析　本题主要考查的是顺序查找和二分查找的算法思想。数据10是数据序列中第3个元素，因此使用顺序查找时，共查找次数为3次，使用二分查找时，依次被访问的数据为15、6、10，即二分查找的次数也为3次。因此，答案为C。 C 例2 在列表lista中存储的数据依次为：88，78，70，65，60，55，51，45，39，28。现使用二分查找算法在列表lista中查找数据51，共需查找的次数为(　　) A.1次 B.2次 C.3次 D.4次 解析　本题主要考查 ... ...