![数据结构-基于C++语言(微课版) 课件 1-1 折半查找_第1页](http://file4.renrendoc.com/view2/M02/02/12/wKhkFmZegMiAXruUAACFIGcVNOQ794.jpg)
![数据结构-基于C++语言(微课版) 课件 1-1 折半查找_第2页](http://file4.renrendoc.com/view2/M02/02/12/wKhkFmZegMiAXruUAACFIGcVNOQ7942.jpg)
![数据结构-基于C++语言(微课版) 课件 1-1 折半查找_第3页](http://file4.renrendoc.com/view2/M02/02/12/wKhkFmZegMiAXruUAACFIGcVNOQ7943.jpg)
![数据结构-基于C++语言(微课版) 课件 1-1 折半查找_第4页](http://file4.renrendoc.com/view2/M02/02/12/wKhkFmZegMiAXruUAACFIGcVNOQ7944.jpg)
![数据结构-基于C++语言(微课版) 课件 1-1 折半查找_第5页](http://file4.renrendoc.com/view2/M02/02/12/wKhkFmZegMiAXruUAACFIGcVNOQ7945.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
折半查找的算法思想;折半查找的实现;折半查找的性能分析。本节目录:本节内容:折半查找有序表的折半查找
有序表的折半查找
使用条件:线性表中的记录必须按关键码有序;必须采用顺序存储。基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。有序表的折半查找
折半查找的基本思想:
[r1………rmid-1]rmid[rmid+1………rn]如果k<rmid如果k>rmid查找左半区查找右半区k(mid=(1+n)/2)有序表的折半查找
例:查找值为14的记录的过程:012345678910111213
7141821232931353842464952low=1high=13mid=7
high=6mid=3
high=2
mid=1
31>1418>147<14low=2mid=2
14=14非递归算法intBinSearch(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{low=1;high=n;while(low<=high){mid=(low+high)/2;if(k<r[mid]) high=mid-1;elseif(k>r[mid]) low=mid+1;else returnmid;}return0;}有序表的折半查找
有序表的折半查找
递归算法intBinSearch(intr[],intlow,inthigh,intk){if(low>high) return0;else{mid=(low+high)/2;if(k<r[mid])returnBinSearch(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch(r,mid+1,high,k);else returnmid;}}有序表的折半查找
折半查找的查找性能可以使用二叉查找树来分析。树中的每个结点对应有序表中的记录的位置。二叉查找树的构造方法:
⑴当n=0时,二叉查找树为空;
⑵当n>0时,二叉查找树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1]~r[mid-1]相对应的二叉查找树,根结点的右子树是与r[mid+1]~r[n]相对应的二叉查找树。有序表的折半查找
11个结点的二叉查找树的构造-11-22-33-44-510-1111-9-108-97-85-66-7内部结点外部结点3691011784512有序表的折半查找
具有n个结点的二叉查找树的深度为h=查找成功:在表中查找任一记录的过程,即是二叉查找树中从根结点到该记录结点的路径,和给定值的比较次数等于该记录结点在树中的层数。查找失败:查找失败的过程就是走了一条从根结点到外部结点的路径,和给定值进行的关键码的比较次数等于该路径上内部结点的个数。从折半查找判定树上容易看出,无论是查找成功还是查找失败,关键码的比较次数都小于等于二叉查找
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- Midjourney关键词魔法运用
- 退税减税降费政策操作指南科技型中小企业研发费用加计扣除政策
- 车辆保险索赔申请书
- 海北市重点中学2024年英语八下期末复习检测试题含答案
- 哈尔滨市呼兰区2024届数学三下期末质量检测试题含解析
- 2023年下半年怀化市事业单位考试《计算机专业知识》试题
- 果洛藏族自治州甘德县2023年三年级数学第二学期期末检测模拟试题含解析
- 贵州遵义市正安县重点中学2025年初三五月适应性考试语文试题文试卷含解析
- 贵州省遵义市汇川区2023年数学三下期末教学质量检测模拟试题含解析
- 人教版三年级数学上册第8单元测试题
- 十字相乘法课件
- 小学生人工智能科普微课教案
- (正式版)JBT 3300-2024 平衡重式叉车 整机试验方法
- 《学会专注高效学习》初中主题班会课件
- (2024年)发生输液反应时应急预案及处理流程
- (2024年)建筑行业财务培训资料
- (2024年)电工安全培训(新编)课件
- 水闸闸门安全制度培训
- 职业竞争力培训课件
- 小学数学教学中学生计算能力的培养与提高探究 论文
- 小班社会《认识交通标志》课件
评论
0/150
提交评论