十、折半查找

概念及算法

折半查找（Binary Search）也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是递增有序的。

折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

动图演示

算法

int BinSearch(RcdType rcd[], KeyType key, int low, int high)
{	//递归实现在有序序列rcd[low...high]中折半查找目标关键字key
	int mid = (low + high) / 2;
	if (low > high) 
		return -1;									//找不到目标关键字，返回-1
	if (rcd[mid].key == key)
		return mid;									//中间关键字与目标关键字匹配，返回中间关键字的下标
	else if (rcd[mid].key > key)					//在前半区折半查找
		return BinSearch(rcd, key, low, mid - 1);
	else
		return BinSearch(rcd, key, mid + 1, high);	//在后半区折半查找
}
	
int BinSearch_ite(RcdType rcd[], KeyType key, int low, int high)
{	//迭代实现在有序序列rcd[low...high]中折半查找目标关键字key
	int mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (rcd[mid].key == key)
			return mid;								//中间关键字与目标关键字匹配，返回其下标
		else if (rcd[mid].key > key)
			high = mid - 1;							//在前半区折半查找
		else
			low = mid + 1;							//在后半区折半查找
	}
	return -1;										//找不到目标关键字，返回-1
}