高中信息技术选修1课件-2.4 查找1-浙教版(共16张PPT+素材)

对分查找算法
如果是你
你会怎么猜价格呢？帐篷价格1000元内。
你的第一次价格报多少？为什么？
第二次呢？为什么？
每猜一个价格的结果
没猜中
猜中
没猜中
为下次猜测减少了一半范围。猜大了，在后半部分，猜小了在前半部分。
猜中
猜中，游戏结束。
猜价格游戏中的算法思想
对
分
找
查
08
猜价格游戏
1-1000是什么？
1-1000都是同类数据
其它顺序可以吗？
升序或降序都可以
他们顺序有关系吗？
从小到大排序
不是递增1的序列可以吗
比如：2、5、6、9、45、87、93、98？
前提条件
变异的猜价格游戏
2
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
5
6
9
45
87
93
98
猜的价格
i=1
j=8
m=4
第一次
数组：
232
i=5
m=6
第二次
i=7
i=8
m=7
第三次
i=9
m=8
第四次
对分查找
实现过程
对分查找实现过程
2
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
5
6
9
45
87
93
98
正确价格
i=1
j=8
m=4
第一次
数组：
6
j=3
m=2
第二次
i=3
m=3
第三次
第四次
任务一
2
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
5
6
9
45
87
93
98
正确价格
数组：
45
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}比较次数
比较范围
中间位
中间数
Key与d（m）的关系
i、j的变化
第一次
i= j=
m=
d(m )=
第二次
i= j=
m=
d(m)=
第三次
i= j=
m=
d(m)=
第四次
i= j=
m=
d(m)=
对分查找实现过程
frank
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
denny
colin
benson
ben
alan
abel
Key
数组：
abel
i=1
j=7
m=4
第一次
i=5
m=6
第二次
i=7
m=7
第三次
任务二
abel
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
alan
ben
benson
colin
denny
frank
Key
数组：
even
i=1
j=7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}比较次数
比较范围
中间位
中间数
Key与d（m）的关系
i、j的变化
第一次
i= j=
m=
d(m )=
第二次
i= j=
m=
d(m)=
第三次
i= j=
m=
d(m)=
第四次
i= j=
m=
d(m)=
对分查找的效率
Key
N个有序数，最快查找次数：
1
N个有序数，最慢查找次数：
int(log2N）+1
任务三
Key
市图书馆共有1024*1024=1048576本书，书名按升序排序，使用对分查找算法查找某本书，每次比较需要10毫秒的时间，无论是否找到，最多需要多长时间就可以保证找到要找的书？使用顺序查找，最多需要多长时间才能找到要找的书？顺序查找平均查找时间是多少？
对分查找最多查找时间：（Int(log21048576)+1）*10/1000秒=0.21秒
顺序查找最多查找时间：1048576*10/1000秒=175分种
顺序查找平均时间：（1048576+1）/2*10/1000秒=87分种
对分查找描述
Key
怎样用自然语言对对分查找算法进行描述？
首先将要查找的数与有序数组中间位上的元素进行比较，如果相等，表示找到，否则可以确定要查找的数应该在数组的前半部分或者后半部分继续查找；在新范围内，继续按以上方法进行查找，直到获得最终结果。
小结
Key
对分查找的前提
对分查找的基本思想
对分查找的效率
谢谢聆听