9.2.2　二分查找

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

例如，已知如下11个数据元素的有序表（关键字即为数据元素的值）：

（05，13，19，21，37，56，64，75，80，88，92）

现要查找关键字为21和85的数据元素。

假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即mid＝（low＋hi gh）／2。在此例中，low和high的初值分别为1和11，即［1，11］为待查范围。

下面先看给定值key＝21的查找过程：

首先令查找范围中间位置的数据元素的关键字ST.elem［mid］.key与给定值key相比较，因为ST.elem［mid］.key＞key，说明待查元素若在，必在区间［low，mid－1］的范围内，则令指针high指向第mid－1个元素，重新求得mid＝（1＋5）／2＝3。

仍以ST.elem［mid］.key和key相比，因为STeboST.elem［mid］.key＜key，说明待查元素若存在，必在［mid＋1，high］范围内。则令指针low指向第mid＋1个元素，求得mid的新值为4，比较ST.elem［mid］.key和key，因为相等，则查找成功，所查元素在表中序号等于指针mid的值。

再看key＝85的查找过程：

此时因为下界low＞上界high，则说明表中没有关键字等于key的元素，查找不成功。

二分查找的算法如下。

算法9.2 二分查找

先看上述11个元素的表的具体例子。从上述查找过程可知：找到第⑥个元素仅需比较1次；找到第③和第⑨个元素需比较2次；找到第①、④、⑦和⑩个元素需比较3次；找到第②、⑤、⑧和○11个元素需比较4次。

这个查找过程可用图9－1所示的二叉树来描述。树中每个结点表示表中一个记录，结点中的值为该记录在表中的位置，通常称这个描述查找过程的二叉树为判定树。从判定树上可见，查找21的过程恰好是走了一条从根到结点④的路径，和给定值进行比较的关键字个数为该路径上的结点数或结点④在判定树上的层次数。类似地，找到有序表中任一记录的过程就是走了一条从根结点到与该记录相应的结点的路径，和给定值进行比较的关键字个数为该结点在判定树上的层次数。因此，二分查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为log2n＋1，所以二分查找法在查找成功时和结定值进行比较的关键字个数至多为log2n＋1。

图9－1 二分查找过程

那么，二分查找的平均查找长度是多少呢？一般情况下，表长为n的二分查找的判定树的深度和含有n个结点的完全二叉树的深度相同。

假设n＝2h－1并且查找概率相等，则查找成功时二分查找的平均查找长度为

在n＞50时，可得近似结果

所以二分查找的平均时间复杂度为O（log2n）。二分查找在查找不成功时的关键字比较次数不超过log2n＋1。

折半查找的效率比顺序查找高，但它只适用于有序表，且限于顺序存储结构，对线性链表通常不能进行折半查找。