6.2.2 折半查找

折半查找，又称二分查找，它适用于有序的顺序表。基本思路是：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中（例如，在查找表升序排列时，若给定值key大于中间元素的关键字，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有搜需要查找的元素，则查找不成功，返回查找失败的信息。

int binary_search(SeqList L,ElemType key){
//在有序表L中查找关键字为key的元素，若存在则返回其位置，不存在则返回-1
	int low=0,high=L.tablelen-1,mid;
	while(low<=heigh){
		mid=(low+high)/2;//取中间位置
		if(L.elem[mid]==key)
			return mid;//查找成功并返回所在位置
		else if(L.elem[mid]>key)
			high=mid-1;//从前半部分继续查找
		else
			low=mid+1;//从后半部分继续查找
	}
	return -1;
}

折半查找的过程可用判定树来描述。树中每个原型结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。查找成功是的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功的查找长度为根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于其右子结点值。若有序序列有n个元素，则对应的判定树有n个圆形非叶结点和n+1个方形的叶结点。

用折半查找法查找到给定值得比较次数不会超过树的高度。

在等概率查找时，查找成功的平均查找长度为

ASL=1/n*(l1+l2+……+h*2^(h-1))=[(n+1)/n]*log2(n+1)约等于log2(n+1)-1

式中，h是树的高度，并且元素个数为n时，树高h=log2(n+1) 。所以，折半查找的时间复杂度为O(log2n)，平均情况下比顺序查找的效率高。

因为折半查找需要方便地定位查找区域，所以适合折半查找的存储结构必须具有随机存取的特性，因此该查找法仅适合于线性表的顺序存储结构，不适合链式存储结构，且要求元素按关键字有序排序。