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

对分查找
algorithm
隐藏在游戏中的算法
小游戏体验
猜数字
思考：如何用最少的次数去猜到这个数字？
对分查找的方法
（1）首先将查找的数与有序数组内处于中间位置的数据比较，
如果中间位置上的数与查找的数不同，根据有序性，就可以确
定应该在数组的前半部分或者后半部分继续查找
（2）在确定新范围里，照上述方法继续寻找，直到最终结束
对分查找的过程：key=23
7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
第一次：
i
j
m
Key>a(m)在后半段中寻找
第二次：
7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
j
i
m
Key7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
第三次：
i
m
j
找到了 a(m)=key
讨论总结：
i、j、m在对分查找过程中的变化情况
a(m)>key
i不变
j=m-1
a(m)j不变
i=m+1
如果key的值找不到是怎么样的？
对分查找的过程：key=24
7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
第一次：
i
j
m
Key>a(m)在后半段中寻找
第二次：
7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
j
i
m
Key7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
第三次：
i
m
j
7 13 16 22 23 31 40
a(1) a(2) a(3) a(4) a(5) a(6) a(7)
i
m
j
a(m)=23而 key=24 j不变 i=m+1 i越过了j
查找完，未找到key
结论：
1、 a(m)>key i不变 j=m-1
2、 a(m)3、重复查找的条件是i<=j
利用流程图描述对分算法：
开始
i<=j
m=(i+j)\2
a(m)=key?
Y
N
Y
N
Y
N
结束
未找到
找到
a(m)j=m-1
i=m+1
i=1,j=n
拓展：如果我的数是以降序排列，其中i,j,m的变化情况是否有新变化？如果有，请详述
如果我的数是以降序排列，流程图需要变化吗？如果有，请详述
再 见