有序表上的二分查找

基本思想：

      在一个查找区间中，确定出查找区间的中心位置，用待查找数据元素的关键字和中心位置上数据元素的关键字比较，若两者相等则查找成功;否则若前者小于后者，则把区间定为原查找区间的前半段，继续这样的过程;否则若前者大于后者，则把查找的区间定为原查找区间的后半段，继续这样的过程.这样的查找过程一直进行到查找区间的上界小于查找区间的下界为止.由于二分查找算法每次比较后都把查找区间折半，所以该算法也称做折半查找算法.

 

循环结构的二分查找：

// 在有序表a[0]--a[n-1]中二分查找关键码为key的数据元素，
// 查找成功时返回该元素的下标序号;失败时返回-1
int BiSearch(int a[],int n,int key)
{
	int low=0,high=n-1;
	int mid;
	while (low<=high)
	{
		mid=(low+high)/2; // 确定查找区间
		if(a[mid]==key)return mid; // 查找成功
		else if(a[mid]<key)low=mid+1;
		else high=mid-1;
	}
	return -1; // 查找失败
}

 

递归结构的二分查找：

int BSearch(int a[],int x,int low,int high)
{
	int mid;
	if(low>high) return -1; // 查找不成功
	mid=(low+high)/2;
	if(x==a[mid])
		return mid; // 查找成功
	else if(x<a[mid])
		return BSearch(a,x,low,mid-1); // 在下半区查找
	else
		return BSearch(a,x,mid+1,high); // 在上半区查找
}