4.3.3对半查找算法.ppt_第1页
4.3.3对半查找算法.ppt_第2页
4.3.3对半查找算法.ppt_第3页
4.3.3对半查找算法.ppt_第4页
4.3.3对半查找算法.ppt_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

3 3 3二分法查找 安师大附属复兴中学唐劲松 猜价格 猜价格 游戏规则 1 不能抢答 举手回答 2 5次机会若猜对就把MP3送给你 猜价格 50 75 88 81 84 中间值m m int p1 p2 2 m p1 p2 2或 二分法查找的前提条件 例1 数组有7个元素 依次15 1 2 18 5 10 4 若采用二分法查找在该数组中查找数据10 需要查找的次数是 A 1B 2C 3D 4 注意 二分法查找的数据必须有序 C 1 2 4 5 10 15 18 将查找的数key与有序数组内的中间位置A m 的数据比较若key与A m 相同 则找到 若key与A m 不同 根据数据的有序性 就可确定key在该数组的前半部分还是后半部分 在确定的新范围内 继续按上述方法进行查找 直到获得最终结果 或找不到结果 二分法查找的基本思想 二分法查找的流程图 升序 p1 m 1 p2 m 1 二分法查找的代码 升序 p 0 p1 1 p2 ndowhilep1a m thenp1 m 1elsep2 m 1endifloop 小王去药店买人参 发现店老板称量时的过程是这样子的 先放置100克砝码 砝码偏重 再将砝码改为50克 砝码偏轻 又将砝码改为70克 通过这种策略 老板很快完成称重工作 此过程借鉴的算法是 A 顺序查找B 排序C 二分法查找D 累加 例2 C 例3 我校电子图书馆网站有1000本关于信息技术方面的图书 已索引排序 假设从中取出一条记录并与待查找项比较所花费的时间是10毫秒 则用二分法在该系统中查找任意一本图书最多花费的时间约为 A 100毫秒B 50毫秒C 170毫秒D 110毫秒 查找次数的估算 最少 1次最多 Int log2n 1次 A 一个包含10万个人名的电话簿中找一个电话号码 用二分法查找最多17次就可以找到 将全国13亿人按身份证号排列后 你可以最多进行31次比较后找到这个人的信息 二分法查找的实际意义 效率高 我校首届艺术节马上举行 评委老师正在筛选节目 现评委要查看各节目的资料 表格里是高二年级的9个节目 用二分法查找快速找到6号节目前已经访问了哪几号节目 A 46B 586C 576D 486 例4 C 在筛选时 8个评委老师对6号节目进行打分 成绩分别为采用二分法查找成绩12 8需要几次 A 4B 3C 2D 1 例5 B 总结 顺序查找与二分法查找比较 p1 m 1 p2 m 1 m p1 p2 2或m int p1 p2 2 1次 n次 1次 Int log2n 1次
人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论