浙教版选修一 2.4 查找 课件（15张）

点击添加文本
点击添加文本
点击添加文本
点击添加文本
热身游戏---猜！猜！猜！
5
2
4
8
7
3
对 分 查 找 及 其 程 序 实 现
点击添加文本
点击添加文本
点击添加文本
点击添加文本
目录
对分查找的思想
对分查找的实例
对分查找的过程
对分查找的效率
返回
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的思想
(1).被查找的数组是有序的。
(2).首先将要查找的数与有序数组中间位置的数比较，如果中间位置上的数与查找的数不同，则可确定应该在数组的前半部分还是后半部分继续查找。
(3).在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
返回
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的过程
如果，要查找的值在数组的前半部分。例如：查找22
假设有一组数组a（7），
用于存放升序元素值。用i表示查找范围的起始位置的下标，j表示终止位置的下标,mid表示中间位置元素的下标。
11 22 33 44 55 66 77
第一次查找范围为整组，即a(1)-a(7)，mid=(1+7)\2=4,a(mid)>key，即44>22,比较后j=mid-1
第一次
i
j
mid
第二次
i
j
mid
11 22 33 44 55 66 77
11 22 33 44 55 66 77
第二次查找范围为前半组，即a(1)-a(3) ，mid=(1+3)\2=2,a(mid)=key,找到了！
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的过程
如果，要查找的值为后半部分呢？例如：查找77
11 22 33 44 55 66 77
第一次
i
j
mid
第二次
i
j
mid
11 22 33 44 55 66 77
第三次
i
j
mid
11 22 33 44 55 66 77
第二次查找范围为后半组，即a(5)-a(7) ，mid=(5+7)\2=6,a(mid)第一次查找范围为整组，即a(1)-a(7)，mid=(1+7)\2=4,a(mid)第三次查找范围为a(7)-a(7) ，即a(7)元素，mid=(7+7)\2=7,a(mid)=key,即77=77，找到了！
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的过程
如果，要查找的值不在该数组中呢？例如：查找50
11 22 33 44 55 66 77
第一次
i
j
mid
第二次
i
j
mid
11 22 33 44 55 66 77
第三次
i
j
mid
11 22 33 44 55 66 77
第二次查找范围为后半组，即a(5)-a(7)，mid=(5+7)\2=6,a(mid)>key，即66>50,比较后j=mid-1 ,即j=5
第一次查找范围为整组，即a(1)-a(7)，mid=(1+7)\2=4,a(mid)还有第四次查找吗？为什么？查找何时停止？
第三次查找范围为a(5)-a(5)，即a(5)元素，mid=(5+5)\2=5,a(mid)>key，55>50,比较后j=mid-1,即j=4
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的过程
归纳：
当数组内元素值为升序排列时
(1)如果key(2)如果key>a(mid),新查找的范围为后半部分,j值不变,i=mid+1
(3)
①如果找到了,查找会结束；
②查找范围大于等于一个元素时,即在i<=j时重复查找,如果查 找完最后一个元素，即i>j还是找不到,查找也会结束
返回
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的流程图
开 始
结 束
i?1,j?n
j?m-1
计算中点m?(i+j)\2
i?m+1
a(m)=key
i<=j
Key未找到，输出信息
找到，输出信息
Y
N
Y
N
Y
N
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的程序实现
开 始
结 束
i?1,j?n
j?m-1
m?(i+j)\2
i?m+1
a(m)=key
i<=j
Key未找到，输出信息
找到，输出信息
Y
N
Y
N
Y
N
假设有7个数据已经按升序存放数组a中，查找值为key.
i=1:j=7 ’查找区间初始化
Xb=0 ’记录查找成功时的下标
Do while
’计算出中间位置
if a(m)=key then
xb=m
exit do
end if
if then
’准备在左半区继续查找
else
’准备在右半区继续查找
end if
Loop
i<=j
m=(i+j)\2
Keyj=m-1
i=m+1
改为:key>a(m)
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的效率
提问：利用对分查找法，在n个数据的数组中，我们查找一个数据到底最多要查找多少次呢？
回答：也就是最多查找log2n次！
提问：刚才我们在11，22，33，44，55，66，77数组中查找数据，利用对分查找最多查找了多少遍？
如果再让你利用对分查找法猜我手里的彩票末尾数字，你最多猜几次猜中？
返回
点击添加文本
点击添加文本
点击添加文本
点击添加文本
对分查找的实例
(1).小王用天平称量物品的过程如下：先放置100克砝码，再将砝码改为50克，又将砝码改为75克…….通过这种策略，小王很快完成物品称重工作，此过程借鉴的算法是？
(2).某大学的学生数据库中，包含3000条学生记录。如果取出一条记录并与制定学号进行比较要花10毫秒时间，如果采用对分查找，最多只要检查多少个表项就能找到目标记录？
*(3). 10万大军三天内完成验血找出传染源的问题（详见书本44页实践体验）
验血问题
点击添加文本
点击添加文本
点击添加文本
点击添加文本
回顾
对分查找的思想
对分查找的过程
对分查找的效率