改进的二分法查找

摘要：

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

关键词：查找、二分法、有序数列、算法

所属期刊栏目：32

分类号：TP312(计算技术、计算机技术)

资助基金：中国科学院资助项目60496321;科技部专项基金2001CCA0300;上海市科技发展基金025115032

在线出版日期：2006-06-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：60-62,118