已阅读5页,还剩4页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
9.2.2 折半查找(二分查找),适用条件: 线性表中的记录必须按关键码有序; 必须采用顺序存储。,基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。,例:查找值为14的记录的过程:,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,1431,1418,147,14=14,例:查找值为22的记录的过程:,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3122,1822,2322,2122,lowhigh,int BinSearch1(int r , int n, int k) /数组r1 rn存放查找集合 low=1; high=n; while (lowrmid) low=mid+1; else return mid; return 0; ,折半查找非递归算法,int BinSearch2(int r , int low, int high, int k) /数组r1 rn存放查找集合 if (lowhigh) return 0; else mid=(low+high)/2; if (krmid) return BinSearch2(r, mid+1, high, k); else return mid; ,折半查找递归算法,折半查找判定树,判定树:折半查找的过程可以用二叉树来描述,树中的每个结点对应有序表中的一个记录,结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树,简称判定树。, 当n=0时,折半查找判定树为空; 当n0时,折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树,根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,判定树的构造方法,判定树的构造方法(例:11个结点的判定树),具有n个结点的折半查找判定树的深度为,查找成功:在表中查找任一记录的过程,即是折半查找判定树中从根结点到该记录结点的路径,和给定值的比较次数等于该记录结点在树中的层数。,查找不成功:查找失败的过程就是
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 第6课 植物养护基础知识 课件 2023-2024学年苏教版中劳动技术七年级下册
- 有关劳动合同
- 钢材销售合同5篇
- 2023年化妆品销售年终工作总结报告
- 2023年化学教育教学经验总结
- 垃圾焚烧炉相关行业投资方案
- 护栏清洗车相关行业投资方案范本
- 医用中心吸引系统行业相关投资计划提议范本
- 人教版二年级数学下册课件《用乘法口诀求商 第1课时》
- 在线供应链协同核算体系
- 《我们的公共生活》单元作业设计
- 特许经营与加盟创业知到章节答案智慧树2023年安徽财贸职业学院
- 二年级应用题练习
- 北京林业大学毕业答辩PPT模板
- 跨文化交际智慧树知到答案章节测试2023年苏州大学
- 2015上海三校生数学真题(含详解)
- 科隆流量计选型手册
- 幼儿园幼小衔接经验交流汇报
- 2022年菏泽市护理技能大赛理论考试题库大全-上(单选题)
- 2023年体育单招数学试题与答案
- GB/T 32722-2016土壤质量土壤样品长期和短期保存指南
评论
0/150
提交评论