一种查找算法的改进方法  

A improved method of the bisearch algorithm

作　　者：王海涛[1] 常春勤[2] 

机构地区：[1]河南理工大学计算机学院,河南焦作454003 [2]河南理工大学测绘与国土信息工程学院,河南焦作454003

出　　处：《河南理工大学学报（自然科学版）》2008年第3期324-327,共4页Journal of Henan Polytechnic University（Natural Science）

基　　金：国家科技攻关计划项目(2004BA907A20)

摘　　要：折半查找算法是数据结构中有序序列查找中的一个重要算法,此算法在含有n个元素的有序序列中查找某一个元素时,最大循环比较次数为└log2n」+1.但是在很多情况下,查找之前有序序列分布的很多信息为已知,如当知道了有序序列中每相邻2个元素之差最大值的一个上界,就可以有比折半法更加有效的查找算法.以此改进的折半法查找性能明显优于原算法的查找.受序列分布的影响,其在最坏情况下查找一个元素的最大比较次数在1和└log2n」+1之间,明显优于折半查找.此方法在实际应用中可极大提高查找效率.Bisearch algorithm is an important search algorithm in the sequence array of data structure, which most cyclic compared time is [ log2n]J ＋ 1 when algorithm searches a special element among some ones. But, some information is already known in many circumstance , such as a upper bound of the maximum difference between adjacent element in the array. Then, a preferable algorithm is designed. The improved bisearch algorithm is better than the old one in the performance of searching. Under the array distributing effect, in the worst case, the maximum times of comparison is between 1 and L log2n] ＋ 1 at the time of searching special element. The performance efficiency is improved obviously at applications.

关 键 词：算法 查找 折半算法 有序序列 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]