目录
情境设置：
第一种方案：一一对比
函数递归：
函数递归有两个必要条件：
第二种方案一一对比的进阶版--函数递归
图解：
第三种方案：二分查找
二分查找主要的流程
第四种方案二分查找进阶方案--函数递归
图解：
总结：
情境设置：
从一组有序数组中1，2，3，4，5，6，7，8，9，10中找数字。
第一种方案：一一对比Step1,将有序的数字放到数组中
Step2,设置循环，一个一个的与要找的数进行比较。
int main()
{
int arr[] = {1,2,3,4,5,6,7,8,9,10};//将有序的数字放到数组中。
int i = 0;//要查找的数字
int n = 0;
int sz = sizeof(arr) / sizeof(arr[0]);//求数组中元素个数
scanf("%d", &i);
for (n = 0; n < sz; n++)
{
if (arr[n] == i)
{
printf("找到了，下标为%d", n);
break;
}
}
if (n > 9)
printf("找不到");
return 0;
}
函数递归：
什么时候可以用函数递归呢？
在我看来，重复执行某一些相同或者类似的”动作“，可以考虑函数递归。
函数递归的中心思想就是大事化小，个人理解就是将我们重复执行的一些相同的或者类似的“动作”，作为一个动作，反复执行。（有点像循环，但不一样）
函数递归有两个必要条件：1.每一次递归之后，我们都要离递归结束的条件（限制条件）越来越近。
2.需要有一个限制条件，使我们的递归结束
第二种方案一一对比的进阶版--函数递归我们来分析下：
重复动作：一个一个比较，我们一直在重复这个动作
限制条件的设置：我们什么时候会不比较了呢？要么是找到了,要么是没找到的时候。
我们来看代码
#include图解：int search(int* pa,int k,int sz)// pa是指针指向首元素(arr[0])的地址 { //比较的是 当前进入函数pa所指向的地址，与arr[10]的地址的地址比较 //pa+sz 每一次递归进来都是arr[10]的地址 if ( pa <= (pa+sz) ) //限制条件:每一次递归进来，判断有没有越界 { if (*pa != k) //判断当前地址所指向的元素是不是与要找的k相同 return 1 + search(pa + 1, k,sz-1); //pa+1-->每递归一次，pa指向后面一个元素的地址 //sz-1-->保证了每次递归之后 pa+sz 指向的都是arr[10]的地址 else return 0; } else return 0; //只要每没有找到，返回0 } int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//13 int sz = sizeof(arr) / sizeof(arr[0]) - 1; // sz-->数组的最大下标-->先求的是数组元素个数，再减一。 int k = 0; scanf("%d", &k); int ret = search(arr,k,sz); //参数分别为 数组首元素的地址 要找的数 数组的最大下标 if (ret > 9) printf("找不到"); else printf("找到了，下标为%d", ret); return 0; }
①②...表示每一次递推的顺序
紫色的1，2，3，4...是返回的值
这里是k > 10 的情况
红色线代表递推出去，紫色线代表回归。
为什么ret接收的是10呢？(可以打开监视测试一下)，我们search函数进去了11次， ，回去的时候也是11次。回去的时候呢，有10次是return 1+search() , 1次是 结束函数递归的时候，return 0 ;
所谓递归，一去一回。从哪里进来的，回哪里去，每一次回归，都是回到 return 1+ search(pa+1,k,sz-1)的地方
第三种方案：二分查找一一对法，太过繁琐，每一次都需要比较很多的值才能确定有没有我们要找的数字。
我想大家应该有玩过猜数字的游戏吧。1-100之间的数字，让你去猜，你为了缩小范围先猜50，在看看大了还是小了，在缩小一半，以此类推。
这就是我们的二分查找。
二分查找主要的流程知左(右)下标，求中间下标，在比较。比较一次，没找到，看k(要找的数)是在中间数的左边还是右边，调整左下标或者右下标，再求中间下标，再比较。一直重复这个动作。直到有一次，我们左下标大于右下标，结束。
int mid_search(int arr[],int sz,int k)
{
int left = 0;//最左边的下标
int right = sz - 1;//最右边的下标
while (left <= right)//循环的限制条件
//在每一次找不到的时候，left或者right会发生改变，直到不满足条件为止，跳出循环
{
int mid = left + (right - left) / 2;//找出中间元素的下标
if (arr[mid] > k)//用中间元素与我们要比较的值判断
//中间值大，则说明k可能在中间值的右边
right = mid - 1;//调整我们的最右边的下标
else if (arr[mid] < k)
//中间值小，则说明k可能在中间值的左边
left = mid + 1;//调整我们最左边的下标
else
return mid;//找到了就会返回中间元素的下标
}
//如果没找到，我们的 left 将会大于 right 跳出循环
return 10;//没找到的时候，返回值与if(ret>9)相呼应
}
int main()
{
int arr[] = {1,2,3,4,5,6,7,8,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);//求出数组中元素的个数
int k = 0;
scanf("%d", &k);
int ret = mid_search(arr,sz,k);
//函数参数分别为 数组首元素地址，元素个数，要找的数
if (ret>9)
printf("找不到");
else
printf("找到了，下标为%d",ret);
return 0;
}
简单图解 ：
第四种方案二分查找进阶方案--函数递归int mid_search(int left, int right,int* pa,int k)
{
int mid = left + (right - left) / 2; //找中间的数的下标
if (left <= right)
{
if (*(pa + mid ) < k)
{
left = mid + 1;
return mid_search(left, right, pa, k);
}
else if (*(pa + mid ) > k)
{
right = mid - 1;
return mid_search(left, right, pa, k);
}
else
return mid;
}
ruturn 10; //根据我们主函数中的判断的条件设置
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 0;
int left = 0;
int right = sizeof(arr) / sizeof(arr[0]) - 1;
scanf("%d", &k);
int ret = mid_search(left,right,arr,k);
//参数为左下标，右下标，首元素地址，要查找的数
if (ret>=10)
printf("找不到");
else
printf("找到了，下标为%d", ret);
return 0;
}
图解：
解释：红色线是递推，橙色线是回归。
总结：我们讲了从有序数组中查找数字的4种方法。
一一对比和进阶版，二分查找和进阶版
让我们更深入了解函数递归。
函数递归，既有递推，又有回归。回归的时候，从哪里来回哪里去。
