第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: | 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: |
学科网(北京)股份有限公司
print(”查找成功! ”) else: print(”未找到! ”) | 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个已按升序排序的数据。使用二分查找时,把查找
学科网(北京)股份有限公司