程序员考试考点：二分法查找

二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中的结点按关键字排序，并且要用向量作为表的存储结构。

二分法查找的基本思想如下(设R[low,…，high]是当前的查找区间)。

(1)确定该区间的中点位置：mid=[(low+high)/2];

(2)将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：

若R[mid].key>k,则由表的有序性可知R[mid,…，n].key均大于k,因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…，mid-1]中。因此，新的查找区间是左子表R[low,…，high],其中high=mid-1.

若R[mid].key

若R[mid].key=k,则查找成功，算法结束。

(3)下一次查找时针对新的查找区间进行，重复步骤(1)和(2)。

(4)在查找过程中，low逐步增加，而high逐步减少。如果high

因此，从初始的查找区间R[1.…，n]开始，每经过一次与当前查找区间中点位置上的结点关键字比较，就可以确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为k的结点，或者直至当前的查找区间为空(即查找失败)时为止。

例如，我们要在{11.13.17.23.31.36.40.47.52.58.66.73.77.82.96.99}中查找58的过程如图1-19所示(粗体表示mid位置)。在上述序列中查找35的过程如图1-20所示。

图1-19 二分法查找58 图1-20 二分法查找35

二分法查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。要注意的是，判定树的形态只与表结点的个数n相关，而与输入实例中R[1.…，n].key的取值无关。

设内部结点的总数为n=2h–1.则判定树是深度为h=log2 (n+1)的满二叉树。树中第k层上的结点个数为2k–1.查找它们所需的比较次数是k.因此在等概率假设下，二分法查找成功时的平均查找长度约为log2 (n+1)–1.二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度，即为[log2 n]+1.二分法查找的最坏性能和平均性能相当接近。

虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费o(nlog2n)的时间。二分法查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。

对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。