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

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