5.2.2 二分查找 课件(共38张PPT)

(课件网) 5.2.2 二分查找 年 级：高一 学 科：信息技术（粤教版） 二分查找 binary search 例 给定一个数组 和整数 求使得 问题 求 将问题具体化 试 顺序查找 解 顺序查找 解 顺序查找 解 顺序查找 解 析 数组 最优： 最劣： 平均： 顺序查找的效率 例 给定一个数组 和整数 该条件未被使用 求使得 顺序查找的低效之处 二分查找 解 中间查找成功 中间元素 则右半边元素均 二分查找 解 二分查找 解 二分查找 解 则左半边元素均 二分查找 解 二分查找 解 二分查找 解 二分查找 解 二分查找 解 A 为空，则 不存在 二分查找 解 一空，则 存在，算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 二分查找全过程 结 中有 个元素，则每次操作： 要么找到了 要么舍弃了中至少的元素 故最多查找 二分查找的效率 析 代码实现 例 给定一个数组 和整数 求使得 最小 问题 一空，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 原二分查找全过程 结 析 则将查找范围缩减为 可以丢吗？ 尝试修改 析 对，由于，且 故 尝试修改 析 则将查找范围缩减为 尝试修改 析 则将查找范围缩减为 可以丢 则将查找范围缩减为 尝试修改 一空，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 修改后二分查找全过程 结 一空，则算法终止；若，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 再次修改后二分查找全过程 结 尽管二分查找的基本思想相对简单，但其细节可以令人难以招架 ... ———高德纳 一空，则算法终止；若，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 错在哪儿？ 结 一空，则算法终止；若，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 错在哪儿？ 结 一空，则算法终止；若，则算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 错在这儿 结 一空，则算法终止；若，则比较算法终止 二 则 算法终止 则将查找范围缩减为回到第一步 则将查找范围缩减为回到第一步 正确答案 结 总结 请用代码实现例2中修改后的二分查找算法 若求的是最小的，应该如何修改原二分查找算法？请给出修改后的算法过程。 请用代码实现2中的算法 课后作业