一种查找算法的改进方法

• 作者: 常春勤 王海涛
• 来源期刊: 河南理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 算法 查找 折半算法 有序序列
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 机电工程
• 页码范围: 324-327
• 页数: 4页
• 分类号: TP312
• 字数: 2687字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-9787.2008.03.014

摘要

折半查找算法是数据结构中有序序列查找中的一个重要算法,此算法在含有n个元素的有序序列中查找某一个元素时,最大循环比较次数为「log2n」+1.但是在很多情况下,查找之前有序序列分布的很多信息为已知,如当知道了有序序列中每相邻2个元素之差最大值的一个上界,就可以有比折半法更加有效的查找算法.以此改进的折半法查找性能明显优于原算法的查找.受序列分布的影响,其在最坏情况下查找一个元素的最大比较次数在1和「log2n」+1之间,明显优于折半查找.此方法在实际应用中可极大提高查找效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王海涛	河南理工大学计算机学院	20	262	6.0	16.0
2	常春勤	河南理工大学测绘与国土信息工程学院	9	70	5.0	8.0