二分查找的递归与非递归_治算法——二分查找法 递归 非递归

之前写过二分查找的代码，但一直没有总结。今天就先总结一下二分查找的递归与非递归的实现。

一、关于二分查找的算法

1.二分查找的条件：必须是一组有序的数据（升序或降序）

2.二分查找也称折半查找，其算法就是（以一组升序的数据来解释）：

a.每次先找出这组数据的中间数（mid）；

b.如果要查找的数据（num）小于 mid ，那么就在前一半数据中查找；如果要查找的数据（num）大于 mid ，那么就在后一半数据中查找；

c.继续重复上述步骤，直到找到为止，此时返回数据的位置；找不到返回空。很明显，这样就大大提高了查找的效率。

可以用这幅图简单来表示一下:

举个例子：例如要在数组a=｛1,2,3,4,5,6,7,8,9｝中查找 2 这个数，那么就要先找出中间数 5 ，由于 2<5 ,那么应该在该数据的前一半（1~5）查找，然后继续重复上述工作...

二、代码实现

非递归：

//非递归
int bin_search(int *arr,int sz,int num)
{
	assert(arr);
	int left = 0;<span style="white-space:pre">	//每段数据的左端</span>
	int right = sz-1;<span style="white-space:pre">	//每段数据的</span>右<span style="white-space:pre">端</span>
	int mid = 0;
	while (left <= right) 
	{
		mid = (left+right)/2;	//中间位置每次都在变
		if (num == *(arr+mid))
		{
			return mid;
		}
		else if (num < *(arr+mid))
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
		
	}
	if(left > right)
		return NULL;
	else
		return mid;
}

//递归
int bin_search(int* arr, int left, int right, int num)
{
	assert(arr);
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right)/2;
		if (num == *(arr+mid))
		{
			return mid;
		}
		else if (num < *(arr+mid))
		{
			return(bin_search(arr,left,mid,num));
		}
		else
		{
			return(bin_search(arr,mid,right,num));
		}
	}
	return NULL;
}