折半查找效率浅析

摘 要：折半查找法是效率较高的一种查找方法，它要求查找表是顺序存储的有序表。折半查找法特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 本文以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）所示。

这个判定树与霍夫曼树的区别在于折半查找的判定树的内节点也是待查找元素，而叶子节点是区间。因此折半查找与BST更相似，只不过折半查找的判定树是固定的，不是动态结构。另一个区别在于折半查找是以元素的序号来区分的，而BST的元素序号与其位置没有关系，BST元素的键值决定了其位置，而且键值没有二分关系。

三、折半查找法效率分析

先看{1，16，21，35，46，58，62，76，80，98，120，180}12个元素的查找表的具体例子。 从上述查找过程可知：找到第⑥个元素仅需比较1次；找到第③和第⑨个元素需比较2次；找到第①、④、⑦和⑩个元素需比较3次；找到第②、⑤、⑧…需比较4次。这个查找过程可用图1（d）所示的二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树，从判定树上可见，查找35的过程恰好是走了一条从根到结点④的路径，和给定值进行比较的关键字个数为该路径上的结点数或结点④在判定树上的层次数。因此，折半查找法在成功时进行比较的关键字个数最多不超过树的深度，依此类推，可得等概率情况下查找成功时的ASL为

接下来讨论失败的情况， 在折半查找判定树中，查找失败时的比较次数即是查找相应外结点时与内结点的比较次数。如果在图1（d）所示的判定树中所有结点的空指针域上加一个指向一个方形结点的指针，形成如图1（e）所示，并且称这些方形结点为判定树的外部结点（与之相对，称那些圆形结点为判定树的内部结点），那么折半查找时查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。例如，查找25的过程即为走了一条从根到外部结点的路径，比较3次失败；查找180的过程即为走了一条从根到外部结点的路径，比较4次失败。这样的外部结点共有13个，因此可得等概率情况下查找失败时的ASL为

折半查找判定树是一棵二叉排序树，折半查找判定树中的内结点都是查找成功的情况，所有外部结点是查找失败的情况。

四、结语

虽然折半查找法的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O（nlgn）的时间。折半查找只适用顺序存储结构，为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，折半查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 本文以12个记录为例，分析了折半查找法过程中形成的判定树，并详细地分析了查找成功时和查找失败时的ASL。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1998.

[2] 方铖.一种改进的折半查找算法[J]. 现代电子技术. 2008（05）.

[3] 魏少涵.折半查找算法在最优化问题中的应用[J]. 计算机时代. 2012（09）.

[4] 时百胜.基于概念的折半查找算法[J]. 计算机科学. 2009（06）.

[5] 邹国霞，唐建清.索引折半查找算法的研究与设计[J]. 计算机时代. 2009（12） .

[6] 孙义欣.用C#实现折半查找算法的可视化演示[J]. 电脑知识与技术. 2011（29）.

[7] 柳海燕.基于C#的折半查找算法动态演示程序[J]. 电脑知识与技术. 2011（23）.

[8] 王钢，徐红主编.数据结构[M]. 清华大学出版社， 2005.