教学课件：查找及二分法（茂名202307）凌艺荧.pptx

常见算法应用 查找及二分法 讲课人：凌艺荧 静态查找表 动态查找表 查找 查找 (search) 是在一个数据结合中查找满足给定条件的记录。 查找表 查找表 (Search Table) 是由同一类型的数据元素(或记录)构成的集合。 ·查询某个数据元素是否在查找表中 ·检索某个数据元素的属性 · 向查找表中添加一个数据元素 ·从查找表中删除一个数据元素 查找和查找表 查找算法 (平均)时间复杂度 空间复杂度 条件 顺序查找 O(n) O(1) 二分查找 O(log2n) O(1) 插值查找 0(log2(log₂n)) O(1) 斐波拉契查找 O(log2n) O(n) 分块查找 0(log2n)~O(n) 0(1)~0(n) 树表查找(BST) 0(log2n) O(1) 哈希查找 O(1) O(n) 顺序查找法 顺序查找也称为线形查找，属于无序查找算法。 按照数据在查找表中原有的顺序进行遍历查询的算法。 【例1】 在一个已知的列表[1,3,5,4,2,4,6,5,1]中 查找给定的元素。输出给定元素出现的所有 卜 示 考 给 是 下 要 不 在 干 组 不 检 口 小 o □ , | **输入的给定元素是 int 类型。 顺序查找法 arr =[1,3,5,4,2,4,6,5,1] key = int(input())#输入关键字 for iin range(len(arr)):#顺序遍历列表 if arr[i]== key:#只要关键字与当前元素相 等，就输出当前下标 print(i) 顺序查找法 【例2】 在一个已知的列表[1,3,5,4,2,4,6,5,1] 中查找给定的元素出现的第一个位置。如果 给定的元素存在于列表中，输出它的下标； 如果不存在，输出-1。 * * 命 入 幻 给 完 开 要 星 in+ 米 刑 日 四 人 会 儿 大 生 顺序查找法 arr =[1,3,5,4,2,4,6,5,1] t=0 key = int(input())#输入关键字 for i in range(len(arr)):#顺序遍历列表 if arr[i]== key: print(i) t+=1 break #保证只输出第一个位置就跳出遍历循环 if t==0: print(-1)#关键字不存在于列表中 顺序查找法 应用 — — 茂名市2021年初中信息技术学科素养展示 【题目描述】 某市2021年开展初中语文学科阅读素养展评活动，请你 根据组委会的需要，编制程序帮助组委会更好地完成工作。 任务2(25分):该活动有“文言文阅读”和“现代文阅读” 两项成绩。请编写程序： (1)录入成绩能自动计算学生总分，并按成绩从高到低 显示。 (输入的样本数据可直接从“程序素材”文件中复制) (2)输入参评号，能显示参评学生成绩。 如 ： 输入参评号：004 输出：参评号 姓名 文言文现代文总分 004 秦才 70 85 155 输出样本数据： 参评号姓名 文言文 现代文 总分 005 002 001 004 003 田升 谢工京 韦天 秦才 许双 85 80 78 70 65 90 90 85 85 75 175 170 163 155 140 输入样本数据： 001 韦天 78 85 002 谢工京80 90 003 许双 65 75 004 秦才 70 85 005 田升 85 90 二分查找法 也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某 一特定元素target 的搜索算法。搜索过程从数组的中间元素middle 开 始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一 特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那 一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤 数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩 小一半。 编写程序，要求 输出特定元素的 数值和下标。