摘要
当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找(binarysearch)是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为??logn??+1。在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算法。改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和??logn??+1之间,明显优于二分查找的??logn??+1。在实际应用中利用改进的二分法可以极大地提高查找效率。
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 [logn]＋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 [logn]＋1, obviously better than binary search.
出处
《计算机工程》
EI
CAS
CSCD
北大核心
2006年第10期60-62,118,共4页
Computer Engineering
基金
国家自然科学基金资助项目(60496321)
科学技术部基础研究重大项目前期研究专项基金资助项目(2001CCA0300)
上海市科技发展基金资助项目(025115032)
关键词
查找
二分法
有序数列
算法
Search
Binary search
Sorted array
Algorithm
