之前写过二分查找的代码，但一直没有总结。今天就先总结一下二分查找的递归与非递归的实现。
一、关于二分查找的算法
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;
}