改进的二分法查找

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

Modified Binary Search

Consider the problem of determining whether a given element x is in array. To solve the search problem, there are many algorithms. And binary search is the most common search algorithm if the array is sorted. The number of comparisons performed by binary search on a sorted array of size n is at most ?? log n ?? +1. The time cost of binary search reaches the lower bound of the search problem. But in many circumstances, some information about the array before search is known. If the upper bound of the maximum difference between any adjacent elements in the array is known, one can design a preferable algorithm. It is referred as modified binary search. In the worst case, the maximum number of comparisons performed by modified binary search is between 1 and ?? log n ?? +1, obviously better than binary search.