5.1顺序查找算法及分析（Python进阶-数据结构与算法）课件

顺序查找与二分查找算法及分析 数据结构与算法（Python版） ❖ 如果数据项保存在如列表这样的集合中， 我们会称这些数据项具有线性或者顺序关 系。 ❖ 在Python List中 ， 这些数据项的存储位 置称为 下标（index） ， 这些下标都是有 序的整数。 ❖ 通过下标 ， 我们就可以按照顺序来访问和 查找数据项 ， 这种技术称为“顺序查找” 顺序查找Sequential Search 数据结构与算法（Python版） 0 ❖ 要确定列表中是否存在需要查找的数据项 首先从列表的第1个数据项开始， 按照下标增长的顺序，逐个比对数据项， 如果到最后一个都未发现要查找的项，那么查找 失败。 顺序查找Sequential Search 数据结构与算法（Python版） 0 数据结构与算法（Python版） 顺序查找：无序表查找代码 下标顺序增长 0 ❖ 要对查找算法进行分析 ， 首先要确定其中 的基本计算步骤。 ❖ 回顾第二章算法分析的要点 ， 这种基本计 算步骤必须要足够简单 ， 并且在算法中反 复执行 ❖ 在查找算法中 ， 这种基本计算步骤就是进 行数据项的比对 当前数据项等于还是不等于要查找的数据项，比 对的次数决定了算法复杂度 数据结构与算法（Python版） 顺序查找：算法分析 0 ❖ 在顺序查找算法中 ， 为了保证是讨论的一 般情形 ， 需要假定列表中的数据项并没有 按值排列顺序 ， 而是随机放置在列表中的 各个位置 换句话说，数据项在列表中各处出现的概率是相 数据结构与算法（Python版） 顺序查找：算法分析 0 同的 ❖ 数据项是否在列表中 ， 比对次数是不一样 的 ❖ 如果数据项不在列表中 ， 需要比对所有数 据项才能得知 ， 比对次数是n ❖ 如果数据项在列表中 ， 要比对的次数 ， 其 情况就较为复杂 最好的情况，第1次比对就找到 最坏的情况，要n次比对 数据结构与算法（Python版） 顺序查找：算法分析 0 ❖ 数据项在列表中 ， 比对的一般情形如何？ 因为数据项在列表中各个位置出现的概率是相同 的；所以平均状况下，比对的次数是n/2； ❖ 所以 ， 顺序查找的算法复杂度是O(n) ❖ 这里我们假定列表中的数据项是无序的， 那么如果数据项排了序 ， 顺序查找算法的 效率又如何呢？ Case Best Case Worst Case Average Case item is present 1 n n/2 item is not present n n n 数据结构与算法（Python版） 顺序查找：算法分析 0 ❖ 实际上 ， 我们在第三章的有序表Search 方法实现中介绍过顺序查找 当数据项存在时，比对过程与无序表完全相同 不同之处在于，如果数据项不存在，比对可以提 前结束 • 如下图中查找数据项50，当看到54时，可知道后面 不可能存在50，可以提前退出查找 数据结构与算法（Python版） 顺序查找：算法分析 0 数据结构与算法（Python版） 顺序查找：有序表查找代码 提前退出 0 Case Best Case Worst Case Average Case item is present 1 n n/2 item is not present 1 n n/2 ❖ 实际上 ， 就算法复杂度而言 ， 仍然是O(n) ❖ 只是在数据项不存在的时候 ， 有序表的查 找能节省一些比对次数 ， 但并不改变其数 量级。 数据结构与算法（Python版） ❖ 顺序查找有序表的各种情况分析 顺序查找：算法分析 0 ❖ 那么对于有序表 ， 有没有更好更快的查找 算法？ ❖ 在顺序查找中 ， 如果第1个数据项不匹配 查找项的话 ， 那最多还有n- 1个待比对的 数据项 ❖ 那么 ， 有没有方法能利用有序表的特性 ， 迅速缩小待比对数据项的范围呢？ 数据结构与算法（Python版） 0 二分查找 # ❖ 我们从列表中间开始比对！ 如果列表中间的项匹配查找项，则查找结束 如果不匹配，那么就有两种情况： • 列表中间项比查找项大，那么查找项只可能出现在 前半部分 • 列表中间项比查找项小，那么查找项只可能出现在 后半部分 无论如何，我们都会将比对范围缩小到原来的一 半： n/2 ○ ❖ 继续采用上面的方法查找 每次都会将比对范围缩小一半 数据结构与算法（Python版） 0 二分查找 数据结构与算法（Python版） 二分查找：代码 0 缩小比对范围 中间项比对 ❖ 二分查找算法实际上体现了解决问题的典 型策略： 分而治之 将问题分为若干更小规模的部分 通过解决每一个小规模部分问题，并将结果汇总 得到原问题的解 数据结构与算法（Python版）