二分查找

/*R[low..high]二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。n/2^k=1，得得k=log2n，时间复杂度可以表示O(logn)*/#include <stdio.h>  //-------------------递归方法----------------------------- int bin_search_recursion1(int array[], int low, int high, int key)  /*传入参数分别是找到的数组Array，数组起始位置，数组结束位置，要找的数*/{	if (low <= high)	{		int mid = low + (high - low) / 2;		if (key == array[mid])			return mid;		else if (key<array[mid])			return bin_search_recursion1(array, low, mid - 1, key);		else if (key>array[mid])			return bin_search_recursion1(array, mid + 1, high, key);	}	else		return -1;}int bin_search_recursion(int array[], int len, int key){	//如果传入的数组为空或者数组长度<=0那么就返回-1。防御性编程  	if (array == NULL || len <= 0)		return -1;	return bin_search_recursion1(array, 0, len - 1, key);}//--------------------------非递归方法------------------------ int bin_search(int array[], int len, int key)  /*传入参数分别是数组地址Array，数组长度len，要找的数据key  返回值为key的位置*/{	//防御性编程  	if (array == NULL || len <= 0)		return -1;	int low = 0, high = len - 1;	int mid;	while (low <= high)	{		mid = low + (high - low) / 2;//为了防止整型变量溢出,用mid=(low+high)/2,low+high可能会大于表达式结果类型所能表示的最大值  		if (key == array[mid])			return mid;		else if (key<array[mid])			high = mid - 1;		else			low = mid + 1;	}	return -1;}int main(void){	int a[6] = { 0,5,20,30,88.102 };	int len = sizeof(a) / sizeof(a[0]);	int locate = 0, locrec = 0;	locate = bin_search(a, len, 88);	locrec = bin_search_recursion(a, len, 20);//根据参数个数选择执行的函数  	PRintf("%d/n", locate);	printf("%d/n", locrec);	return 0;}