原创《折半查找效率》：本论文主要论述了折半查找论文范文相关的参考文献,对您的论文写作有参考作用。
摘 要：折半查找法是效率较高的一种查找方法,它要求查找表是顺序存储的有序表.折半查找法特别适用于那种一经建立就很少改动、而又经常需要查找的线性表. 本文以12个记录为例,分析了折半查找法过程中判定树的形成,并详细地研究了查找成功时和查找失败时的ASL.
关键词：折半查找法；判定树；ASL
The Analysis of The Efficiency of The Binary Search Method
Fang Rui Ying Wu Jun Fang
Wanfang College of Science & Technology HPU
Abstract： The binary search method is an efficient search method and requires that the lookup table is an ordered list of sequential storage. The binary search method is particularly applicable to that by establishing a few changes and often need to find the linear form. This article takes 12 records as an example,analyzes the formation of the decision tree in the process of the binary search method and studies ASL of the success of the search and the failure of the search in detail.
Key Words： the binary search method； the decision tree； ASL
查找,也可称检索,是在大量的数据元素中找到某个特定的数据元素而进行的工作.查找是一种操作,查找的目的在于从一些数据中寻找一个特定的值,这看似简单的工作之所以产生了形形色色的各种方法,无非都是为了追求更高的效率和更方便的操作. 在范围较小的时候,无论采取什么方法查找,所花费的时间都相差无几,在这种情况下,算法上简单易行,且对存储格式要求较低的静态查找无疑就可以满足我们的要求.静态查找是指对查找表只做查询某个“特定的”数据元素是否在查找表中或检索某个“特定的”数据元素的各种属性的“查找”操作,它可以有不同的表示方法,在不同的表示方法中,实现查找操作的方法也不同.对静态查找表可以用顺序表或线性链表进行表示,也可组织成有序的顺序表,或者是索引顺序表,相应的查找方法可采用顺序查找方法、折半查找方法和索引顺序查找的方法.讨论有关静态查找表的折半查找,并计算和分析查找成功时和查找失败时的平均查找长度.如果数列原来是有序的, 则最常用的方法是折半查找法, 也称为二分法查找.
一、折半查找
折半查找法的基本思想是（设R[low..high]是当前的查找区间）：首先确定该区间的中点位置；然后将待查的K值和R[mid].key比较：若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下：
若r[mid].key>K,则由表的有序性可知r[mid..n].key均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表r[1..mid-1]中,故新的查找区间是左子表r[1..mid-1].
若r[mid].key 因此,从初始的查找区间r[1..n]开始,每经过一次和当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,失败则当前的查找区间就缩小一半.这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空（即查找失败）时为止. 假设有已经按照从小到大的顺序排列好的十二个整数a1～a12,要查找的数是X,其基本思想是： 设查找数据的范围下限为low等于1,上限为high等于12,求中点mid等于（low+high）/2,用X和中点元素mid比较,若X等于mid,即找到,停止查找；否则,若X大于mid,替换下限low等于mid+1,到下半段继续查找；若X小于mid,换上限high等于mid-1,到上半段继续查找；如此重复前面的过程直到找到或者low>high为止.如果low>high,说明没有此数. 二、折半查找判定树 判定树的形态只和表结点个数n相关,而和输入实例中r[1..n].key的取值无关.从折半查找法的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作.所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该表再表中的位置,通常称这个描述折半查找过程的二叉树为折半查找判定树. 长度为n的折半查找判定树的构造方法为：当n等于0时,折半查找判定树为空；当n>0时,折半查找判定树的跟结点是有序表中序号为mid等于（n+1）/2的记录,根结点的左子树是和有序表r～r[mid-1]相对应的折半查找判定树,根结点的右子树是和 r[mid+1]～r[n]相对应的折半查找判定树. 例如,长度为12的折半查找判定树的具体生成过程为：在长度为12的有序表中进行折半查找,不论查找哪个记录,都必须先和中间记录进行比较,而中间记录的序号为（1+12）/2等于6（注意是整除即向下取整）,即判定树的根结点是6,如图1（a）所示；考虑判定树的左子树,即将查找区间调整到左半区,此时的查找区间是[1,5],也就是说,左分支上为根结点的值减1,代表查找区间的高端high,此时,根结点的左孩子是（1+5）/2等于3,如图1（b）所示；考虑判定树的右子树,即将查找区间调整到右半区,此的查找区间是[7,12],也就是说,右分支上为根结点的值加1,代表查找区间的高端low,此时,根结点的右孩子是（7+12）/2等于9,如图1（c）所示；重复第二步第三步,依次确定每个结点的左右孩子,如图1（d）所示. 折半查找论文参考资料： 结论：折半查找效率为关于折半查找方面的的相关大学硕士和相关本科毕业论文以及相关折半查找判定树论文开题报告范文和职称论文写作参考文献资料下载。
