一种查找算法的改进方法
- 出版年：2008
- 作者：王海涛；常春勤
- 单位1：河南理工大学计算机学院
- 出生年：1974
- 职称：讲师
- 语种：中文
- 作者关键词：算法；查找；折半算法；有序序列
- 起始页：324
- 总页数：4
- 经费资助：国家科技攻关计划项目(2004BA907A20)
- 刊名：河南理工大学学报（自然科学版）
- 是否内版：否
- 刊频：双月刊
- 创刊时间：1981
- 主管单位：河南省教育厅
- 主办单位：河南理工大学
- 主编：皱友峰
- 地址：河南省焦作市世纪大道2001号
- 邮编：454003
- 电子信箱：zkxb@hpu.edu.cn
- 卷：27
- 期：3
- 期刊索取号：P206.6 718
- 数据库收录：美国《化学文摘》（CA）收录期刊；俄罗斯《文摘杂志》（AJ）收录期刊；美国《剑桥科学文摘》（CSA）收录期刊；《中国矿业文摘》收录期刊；《中国物理文摘》收录期刊；《中国地质文摘》收录期刊；《中国核心期刊（遴选）数据库》收录期刊；《中国学术期刊（光盘版）》暨《中国期刊网》全文收录期刊；《中国科技期刊数据库》全文收录期刊
- 核心期刊：《中国核心期刊（遴选）数据库》收录期刊
摘要
折半查找算法是数据结构中有序序列查找中的一个重要算法，此算法在含有n个元素的有序序列中查找某一个元素时，最大循环比较次数为「log2n」+1．但是在很多情况下，查找之前有序序列分布的很多信息为已知，如当知道了有序序列中每相邻2个元素之差最大值的一个上界，就可以有比折半法更加有效的查找算法。以此改进的折半法查找性能明显优于原算法的查找。受序列分布的影响，其在最坏情况下查找一个元素的最大比较次数在1和Llog2nJ +1之间，明显优于折半查找。此方法在实际应用中可极大提高查找效率。