8.2　折半查找

如果查找表已经按关键字递增（减）有序,则可以采用折半查找的方法。例如,在查词典类的数据表时,很显然不会采取简单的顺序查找方法,这是因为词典中的元素已经按照字母的顺序进行了排列。折半查找也称为二分查找,是一种效率较高的查找方法,但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。

1.折半查找的基本思想

在有序表中,取中间元素作为比较对象,若给定值与中间元素的关键字相等,则查找成功；若给定值小于中间元素的关键字,则在中间元素的左半区继续查找；若给定值大于中间元素的关键字,则在中间元素的右半区继续查找。不断重复上述查找过程,直到查找成功；或者所查找的区域内无数据元素,则查找失败。

2.折半查找的步骤

假设用变量low和high分别表示当前查找区域的首尾下标,该区域的中间元素为mid＝（low＋high）/2。将关键字k与该元素进行比较,根据比较的结果分别进行处理,具体步骤如下。

通过上述过程可知,每通过一次关键字的比较,区域的长度就缩小一半,而区域的个数增加。如此不断进行下去,直到找到关键字为k的元素或当前的查找区域为空（表示查找失败）为止。图8－1所示是在一个有序数组中查找关键字22的过程。

图8－1　折半查找k＝22的过程

3.折半查找的算法

4.折半查找性能分析

从折半查找的过程来看,每次查找都是以表的中点为比较对象,并以中点将表分割为两个子表,对定位到的子表继续作同样的操作。所以,对表中每个数据元素的查找过程,可用二叉树来描述,可以把当前查找区间的中间位置上的记录作为二叉树的根,左子区和右子区中的记录分别作为根的左子树和右子树,由此得到的二叉树称为描述折半查找的判定树或比较树。

具有13个记录的有序表可用图8－2所示的判定树来表示。树中每个结点表示一个记录,结点的编号为该记录在表中的位置,找到一个记录的过程就相当于走了一条从根结点到该记录结点的路径。

图8－2　折半查找的判定树（n＝13）

从图8－2所示的判定树可以看到,与给定值进行比较的次数正好是该结点所在的层次数,查找第一层的根结点31,一次比较即可找到；查找第二层的结点18和42,二次比较即可找到；查找第三层的结点5、23、35、49,三次比较即可找到；查找第四层的结点14、21、29、38、46、52,四次比较即可找到。

查找表中任一元素的过程,即为在判定树中从根结点到该元素结点的路径上各结点关键字的比较次数,也即该元素结点在树中的层次数。对于n个结点的判定树,树高为k,则有2k－1－1＜n≤2k－1,即k－1＜log₂（n＋1）≤k,所以k＝log₂（n＋1）。因此,折半查找在查找成功时,所进行的关键字比较次数至多为log₂（n＋1）。

下面以树高为k的满二叉树（n＝2k－1）为例。假设表中每个元素的查找是等概率的,即p_i＝1/n,则树的第i层有2i－1个结点。折半查找的平均查找长度如下。

所以,二分查找的时间复杂度为O（log₂n）。可见,与顺序查找相比,二分查找的优点是查找速度快,效率高。二分查找的缺点如下。

（1）必须按关键字排序,而排序本身也很费时。

（2）只适用于顺序存储结构,不适合线性链表结构,所以其进行插入、删除操作时必须移动大量的结点。

二分查找适用于那种一经建立就很少改动,而又经常需要查找的线性表。对于那些经常需要改动的线性表,可以采用链表存储结构,进行顺序查找。