5.4数据查找 课件-2022-2023学年浙教版（2019）高中信息技术选修1

5.4数据查找 顺序查找 二分查找 查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个计算步骤。 你能在上图中找到那个特别的数字3吗？ 顺序查找 算法思想 顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。 若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 ①算法简单，对数据是否有序没有要求。 ②查找效率较低，当数据量大时不宜使用。 算法特点 顺序查找 以“在成绩系统中查找某学号”为例，假定某学习小组8名学生的学号数据存储在数组d中，要查找的学生学号（查找键）已经存储在变量key中。 0 1 2 3 4 5 6 7 d 25 22 13 18 14 11 17 19 key 18 0 1 2 3 4 5 6 7 d 25 22 13 18 14 11 17 19 key 15 找到 未找到 你能在上图中找到那个特别的数字3吗？ 顺序查找 将待查找数据存储于数组d中要查询的数据存储于变量key中 ②依次将每个元素与key比较 ③若某个关键字等于键值则查找成功； 所有元素比较完毕仍找不到，则查找失败 顺序查找 将待查找数据存储于数组d中要查询的数据存储于变量key中 ②依次将每个元素与key比较 ③若某个关键字等于键值则查找成功； 所有元素比较完毕仍找不到，则查找失败 #读取数据按行存储到数组d中 #d=[“555555...”,“555555...”,...] flag=False for i in range(len(d)):#遍历每一行 for j in range(__________):#遍历每一列 if : print("3在第%d行,第%d列"%(i+1,j+1)) flag=True break if : print("不存在特殊字符") d[i][j]==”3” flag==False len(d[i]) 枚举算法 顺序查找 小结 1.顺序查找本质上是一种__________思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。 2.一般情况是，当需要查找的数据规模为 n 时，顺序查找最少查找____ 次，最多查找_____次，其平均查找次数是________。 3.顺序查找最大的优点是查找的数据可以是乱序的，但是其缺点是查找效率太低。顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其时间复杂度为_____ 。 枚举算法 1 n (1+n)/2 O(n) 二分查找 算法思想 二分查找又称折半查找，对分查找。它是一种效率很高的查找算法，但被查找的数据序列必须是有序的。 首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。 算法特点 ①要求被查找数据必须有序。 ②查找效率高，适用于大数据查找。 6 12 15 18 22 25 28 35 46 58 60 6 12 15 18 22 25 28 35 46 58 60 6 12 15 18 22 25 28 35 46 58 60 6 12 15 18 22 25 28 35 46 58 60 6 12 15 18 22 25 28 35 46 58 60 二分查找 i j mid Key=12 开始： 第1遍查找： 第2遍查找： 第3遍查找： 第4遍查找： i j 0 1 2 3 4 5 6 7 8 9 10 i j mid i j mid i j mid 二分查找 算法演算 （1）key与d[mid]的大小比较影响下一次查找的范围[i,j]。 ①若d[mid]<key，则查找后半段：i=________，j=______ ②若d[mid]>key，则查找前半段：i=________，j=______ （2）继续重复进行查找的条件。 当i<=j时 （3）对分查找最多的查找次数(n个数据)。 最多次数=int(log2n)+1 ∵n个数据对分x次最后变为1个数据 ∴n/2**x=