c++实现二分查找

原文链接:http://www.cnblogs.com/riasky/p/3429177.html

简要描述:


二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除

困难。

条件:查找的数组必须要为有序数组。

二分查找的过程剩简要描述如下图:

c++实现二分查找

c++实现二分查找

二种实现方式


1.递归

 

/*
arrat:数组 , low:上界;  high:下界;  target:查找的数据; 返回target所在数组的下标 
*/
int binarySearch(int array[], int low, int high, int target) {
	int middle = (low + high)/2;
	if(low > high) {
		return -1;
	}
	if(target == array[middle]) {
		return middle;
	}
	if(target < array[middle]) {
		return binarySearch(array, low, middle-1, target);
	}
	if(target > array[middle]) {
		return binarySearch(array, middle+1, high, target);
	} 
}


 

2.非递归(循环)

 

/*
arrat:数组 , n:数组的大小;  target:查找的数据; 返回target所在数组的下标 
*/
int binarySearch2(int array[], int n, int target) {
	int low = 0, high = n, middle = 0;
	while(low < high) {
		middle = (low + high)/2;
		if(target == array[middle]) {
			return middle;
		} else if(target < array[middle]) {
			high = middle;
		} else if(target > array[middle]) {
			low = middle + 1;
		}
	}
	return -1;
}

 

 

推荐使用非递归的方式,因为递归每次调用递归时有用堆栈保存函数数据和结果。能用循环的尽量不用递归。

 

转载于:https://www.cnblogs.com/riasky/p/3429177.html

上一篇:笔记:Python实现二分查找


下一篇:search-insert-position