折半查找
时间:2009-10-10 作者:smarteng 分类: 经典算法
算法思想:
将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。
折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。
算法步骤描述:
step1 首先确定整个查找区间的中间位置
mid = ( left + right )/ 2
step2 用待查关键字值与中间位置的关键字值进行比较;
若相等,则查找成功
若大于,则在后(右)半个区域继续进行折半查找
若小于,则在前(左)半个区域继续进行折半查找
Step3 对确定的缩小区域再按折半公式,重复上述步骤。最后,得到结果:要么查找成功, 要么查找失败。
折半查找的存储结构采用一维数组存放。
折半查找算法举例
对给定数列(有序){ 3,5,11,17,21,23,28,30,32,50},按折半查找算法,查找关键字值为30的数据元素。
折半查找的算法讨论:
优点: ASL≤log2n,即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
缺点:因要求有序,所以要求查找数列必须有序,而对所有数据元素按大小排序是非常费时的操作。另外,顺序存储结构的插入、删除操作不便利。
考虑:能否通过一次比较抛弃更多的部分(即经过一次比较,使查找范围缩得更小),以达到提高效率的目的。……?
可以考虑把两种方法(顺序查找和折半查找)结合起来,即取顺序查找简单和折半查找高效之所长,来达到提高效率的目的?实际上这就是分块查找的算法思想。
smarteng
人生就流星,虽然转瞬即逝,但也有永恒。
- 使用Erlang的OTP框架创建应用
- php 使用curl模拟登录discuz以及模拟发帖
- 腾讯QQ、阿里旺旺、淘宝、MSN在线状态代码生成
- 新浪微博错误代码解析
- erlang程序设计笔记
- 《HTML 5与CSS 3权威指南》权威的HTML5与CSS3实战教程
- dedecms修改数据库密码配置文件
- 服务器优化小记--Etag和Expires
- 在PHP5中使用PHPMailer发送邮件
- PHP中冒号、endif、endwhile、endfor介绍
- PHP框架——ThinkPHP
- QQ登陆成功返回openId后与网站绑定
- Mediawiki的配置和修改方法
- 使用Golang的官方mock工具--gomock、mockgen
- 用yaf-codes-generator 生成代码
- MacOs 电脑关闭/打开IPV6
- MySQL中datetime和timestamp的区别
- C++声明结构
- 如何保证数据库和缓存的一致性
- 优雅的golang日期时间处理库go-carbon
- API接口纪要
- 解析 Golang 测试(11)- 模糊测试
- 解析 Golang 测试(10)- 什么是好的单测
- 解析 Golang 测试(9)- 一篇文章搞懂 testify
- 解析 Golang 测试(8)- gomonkey 实战
- 解析 Golang 测试(7)- 如何针对 Redis 进行 Fake 测试
- 解析 Golang 测试(6)- 如何针对 MySQL 进行 Fake 测试
- 解析 Golang 测试(5)- MySQL 经典 mock driver—— sqlmock
- 解析 Golang 测试(4)- 一篇文章教你分清 Mock,Stub,Fake
- 解析 Golang 测试(3)- goconvey 实战
- 2023年11月(1)
- 2023年10月(1)
- 2023年3月(2)
- 2023年2月(1)
- 2022年12月(1)
- 2022年9月(13)
- 2022年8月(5)
- 2022年7月(9)
- 2022年6月(2)
- 2022年5月(2)
- 2022年4月(1)
- 2022年3月(2)
- 2021年12月(1)
- 2021年11月(14)
- 2021年10月(2)
- 2021年9月(111)
- 2015年3月(1)
- 2014年5月(4)
- 2014年4月(18)
- 2014年1月(1)
- 2013年11月(2)
- 2013年7月(1)
- 2013年6月(1)
- 2013年3月(13)
- 2013年2月(3)
- 2013年1月(1)
- 2012年12月(8)
- 2012年11月(8)
- 2012年10月(1)
- 2012年9月(13)
- 2012年8月(4)
- 2012年6月(2)
- 2012年5月(10)
- 2012年4月(13)
- 2012年3月(9)
- 2012年2月(8)
- 2011年11月(1)
- 2011年8月(9)
- 2011年7月(8)
- 2011年6月(8)
- 2011年5月(7)
- 2011年4月(19)
- 2011年3月(15)
- 2011年2月(8)
- 2011年1月(9)
- 2010年12月(2)
- 2010年11月(2)
- 2010年10月(2)
- 2010年9月(8)
- 2010年8月(9)
- 2010年7月(1)
- 2010年6月(9)
- 2010年5月(5)
- 2010年1月(7)
- 2009年12月(21)
- 2009年11月(29)
- 2009年10月(100)
- 2009年8月(1)
- 2009年7月(15)
- 2009年6月(52)