改进的二分法查找

• 作者: 朱洪 王海涛
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 查找 二分法 有序数列 算法
• 年，卷（期）: 2006,（10）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 60-62,118
• 页数: 4页
• 分类号: TP312
• 字数: 4482字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2006.10.022

摘要

当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找(binary search)是最常用的.利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为( )logn ( )+1.在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法.文章给出了一个称之为改进的二分法查找算法.改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和( )logn( )+1之间,明显优于二分查找的( )logn( )+1.在实际应用中利用改进的二分法可以极大地提高查找效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王海涛	复旦大学计算机科学与工程系	10	445	6.0	10.0
2	朱洪	复旦大学计算机科学与工程系	29	159	7.0	12.0