改进的二分法查找

摘要

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