7.2 有序表的对分查找
7.2 有序表的对分查找
对分查找也称为折半查找或二分查找，要求线性表中的元素必须已按关键字递增或递减顺序排列。首先用要查找的关键字k与中间位置元素的关键字相比较，这个中间元素把线性表分成两个子表，若比较结果相等则查找完成；若不相等，再根据k与该中间元素的关键字比较的结果确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的元素或者该线性表中没有这样的元素为止。
【例7-2】 在关键字有序序列{2,4,7,9,10,14,18,26,32,40}中采用对分查找法查找关键字为“7”的元素。
解：对分查找过程如图7-2所示。
图7-2 对分查找过程
查找成功，返回序号2。
对分查找的算法如下（在含有n个元素的线性表R中对分查找关键字为k的元素，若找到了，返回其序号i；若找不到，返回-1）：
int BinSearch(LineList R[],int n,KeyType k)
{
int i,low=0,high=n-1,mid;
int find=0; /*find=0表示未找到;find=1表示已找到*/
while(low<=high && !find)
{
mid=(low+high)/2; /*整除取中间值*/
if(k<R[mid].key)
high=mid-1;
else if(k>R[mid].key)
low=mid+1;
else
{
i=mid;
find=1;
}
}
if(find==0)
return(-1);
else
return(i);
}
对分查找过程构成一个判定树，将当前查找区间中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树。例7-2的有序表对应的判定树如图7-3所示。图中大方形表示内部节点，内部节点中的数字表示该记录在有序表中的位置，如0～9表示当前的查找区间是R[0]～R[9]，其中间记录为R[4]。小方形节点表示外部节点，外部节点表示查找不成功出现的情况，如R[3]节点的左边小方形，表示当查找关键字大于R[2].key小于R[3].key时查找失败的情况。
图7-3 R[0]～R[9]的对分查找判定树（n=10）
由此可见，成功的对分查找过程恰好是走了一条从判定树的根到被查记录的路径，经历比较的关键字次数恰为该记录在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部节点的路径，所需的关键字比较次数是该路径上内部节点的总数。
注意：判定树的形态只与表记录个数n相关，而与输入实例中R[n-1].key的取值无关。
算法分析：在对分查找过程中，关键字与k每比较一次，查找范围就缩小一半。每次比较可能涉及的元素个数如表7-1所示。
表7-1 比较次数与可能涉及的元素个数之间的关系
|
比较次数 |
可能涉及的元素个数 |
比较次数 |
可能涉及的元素个数 |
|
1 |
1 |
4 |
8 |
|
2 |
2 |
|
|
|
3 |
4 |
j |
2j-1 |
若有序表中元素个数n正好为：
则对分查找的最大查找长度为：
j=log2(n+1)≈log2n
假设查找每个元素的概率相等，算法恰好是从判定树的根到被查元素的一条路径，而比较的次数恰好是树深。借助于二叉判定树很容易求得对分查找的平均查找长度。平均查找长度为：
其中，Ci是查找R[i]需要比较的次数。因此，对分查找的平均查找长度为O(log2n)，比顺序查找速度快。