算法之二分查找法

【算法解释】：它也被称为折半査找，其优点是查找速度快，缺点是要求所要査找的数据必须是有序序列。

【引入问题】：假如现在我买了一件衣服，你非常好奇的问我多少钱，我说不超过500元。你还是很好奇，我让你接着猜，你才怎么猜呢？答案肯定是你每次猜最中间的数，第一次猜250，假如我有告诉你猜高了，你肯定会在小于250的部分继续除以2进行猜值，这就引入了二分查找的算法。

【查找过程】：假设表中元素是按升序排列，将表中间位置的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置的关键字将表分成前、后两个表，如果中间位置的关键字大于查找关键字，则进一步查找前面的表，否则进一步查找后面的表。一直重复以上过程，直到找到满足条件的关键字，查找成功，或表里没有关键字，查找失败。

【程序设计】

uint8_t binary_search(uint8_t key,int16_t *search_array,uint8_t n)
{
	uint8_t low;
	uint8_t high;
	uint8_t mid;
	uint8_t count;
	uint8_t fail_count;

	count = 0;
	fail_count = 0;
	low = 0;
	high = n-1;
	while(low<high)						/*	査找范围不为0时执行循环体语句*/
	{
		count++;					/*	count记录査找次数*/
		mid=(low+high)/2;				/*	求中间位置*/
		if( key < search_array[mid] )		        /*	key小于中间值时*/
		{
			high=mid-1;				/*	确定左子表范围*/
		}
		else if( key > search_array[mid] )	        /*	key 大于中间值时*/
		{
			low=mid+1;				/*	确定右子表范围*/
		}
		else if( key == search_array[mid] )	        /*	当key等于中间值时，证明查找成功*/
		{
			return key;
		}
	}
	if( fail_count == 0 )					/*	判断是否查找失敗*/
	{
		return FALSE;
	}
	return TRUE;
}

【调用示例】

int main()
{
	uint8_t key = 11;
	int16_t search_array[12] = {1,2,3,4,5,6,7,8,9,10,11};
	uint8_t n = 12;
	printf("	1.二分查找法：");
	key = binary_search(key,search_array,n);
	printf("找到的值是：%d",key);
	printf("\n");
        return 0;
}