一种改进的新二分查找算法的研究与实现  

Research and Realization of a New Improved Binary Search Algorithm

作　　者：罗南超[1] 蹇旭[1] 崔丽[2] 

机构地区：[1]阿坝师范高等专科学校计算机科学系,四川郫县611741 [2]成都职业技术学院软件学院计算机系

出　　处：《计算机时代》2009年第7期56-57,共2页Computer Era

摘　　要：基于传统的二分查找算法,给出了有序表中任意两元素之间距离的最优表示方法,改进了low和high的取值,得到一种基于距离的新二分查找算法。该算法与传统的二分查找算法相比,判定树高度得到有效降低;随着有序表元素的增加,平均查找长度ASL显著减少,查找速度明显提升。On the basis of the traditional binary search algorithm, this paper gives the optimal expression of the distance between any two elements in orderly table, improves the low and high value and gets a new binary search algorithm based on the distance. Comparing the algorithm with the traditional binary search algorithm, the height of decision tree is lowered effectively. With the increasing of the elements in orderly table, the average search length ASL is reduced and the search speed is raised significantly.

关 键 词：有序表 元素 距离 二分查找 判定树高度 ASL 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论] O157.5[自动化与计算机技术—计算机科学与技术]