2020—2021学年 浙教版信息技术选修1 2.4 查找 课件

对分查找 algorithm 隐藏在游戏中的算法 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 小游戏体验 猜数字 思考：如何用最少的次数去猜到这个数字？ 对分查找的方法 （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 Key<a(m)在前半段中寻找 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)=key 讨论总结： i、j、m在对分查找过程中的变化情况 a(m)>key i不变 j=m-1 a(m)<key 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