[C++知识库]（C语言）递归版二分查找

需求：输入一个升序数组，然后键入一个值，程序将会去查找数组中是否有这个值。如果找到了返回下标，如果没找到返回-1；

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>

//目的：输入一个有序数组，查找里面是否有某个值。如果有，返回下标

//数组名，数组长
void input_arr(int arr[], int len)
{
	int i = 0;
	int input = 0;
	for (i = 0; i < len; i++)
	{
		scanf("%d", &input);
		arr[i] = input;
	}
}

//查找的值key，数组名arr，left查找区间最左边的下标，right查找区间最右边的下标
int binary_search(int key, int arr[],int left,int right)
{
	int mid = 0;
    
	while (left <=right)注意这个=不能掉，如果=没了，那么当数组只有一个元素的时候就直接不进入循环，直接return -1了
	{
		mid = (left + right) / 2;
		if (arr[mid] > key)//说明不可能在右边区间找到
		{
			return binary_search(key, arr, left, mid - 1);//注意，这个return 不能去掉，去掉后就会死递归，归不回来了。
		}
		else if (arr[mid] < key)//说明不可能在左边区间找到
		{
			return binary_search(key, arr, mid + 1, right);
		}
		else
		{
			return mid;//不大于也不小于，不就是找到了嘛，找到了直接返回下标
		}
	}
	return -1;//如果while里面没有return mid，也就是没有找到。那么就会走到return -1；
}



int main()
{
	int arr[3] = { 0 };
	int key = 0;//保存查找的值
	int temp = 0;//接收查找的返回值
	int len = sizeof(arr) / sizeof(arr[0]);
	input_arr(arr,len);
	printf("请输入需要查找的值:");
	scanf("%d", &key);

	temp=binary_search(key,arr,0,len-1);//由于查找区间是整个数组arr[0,....,len-1],所以输入0，len-1；
	if (temp != -1)
	{
		printf("找到这个数了，并且下标为：%d\n", temp);
	}
	else
	{
		printf("没找到\n");
	}
	system("pause");
	return 0;
}