高中信息技术选修1课件-2.4查找1-浙教版

对分查找算法 如果是你 你会怎么猜价格呢？帐篷价格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=8m=7第三次 i=9m=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 比较次 数 比较范 围 中间位 中间数 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 比较次数 比较范围 中间位 中间数 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 对分查找的前提 对分查找的基本思想 对分查找的效率 谢谢聆听