二分查找递归与非递归

一、非递归的二分查找

#define _CRT_SECURE_NO_WARNINGS
#include
#include
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int num, right = sizeof(arr) / sizeof(arr[0]) - 1, left = 0, mid=0 ;
	(void)scanf("%d", &num);
	while (left <= right)
	{
		mid = ((right - left)>>1)+left;
		if (arr[mid] == num)
		{
			printf("找到数据%d,位于下标%dn", num, mid);
			break;
		}
		else if (arr[mid] > num)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	while (left > right)
	{
		printf("不存在数据%d", num);
		break;
	}
}

ps:定义左下标和右下标，用两个下标的中间来判断是否等于所要查找的数

用if来判断此时的中间数字与所要查找的数字的大小

如果没有数据则输出不存在数据

二、使用递归的二分查找

//二分查找
#include
int BinarySearch0(int *arr,int  len, int left, int right,int value)
{
	int midIndex = ((right - left) >>1) + left;
	if (left > right)
	{
		return -1;
	}
	if (arr[midIndex] == value)
	{
		return midIndex;
	}
	if (arr[midIndex] > value)
	{
		return BinarySearch0(arr, len, left, midIndex - 1, value);
	}
	else
	{
		return BinarySearch0(arr, len, midIndex + 1, right, value);
	}
	
}
int BinarySearch(int* arr, int len,int value)
{
	int index = BinarySearch0(arr, len, 0, len - 1,value);
	return index;
}
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	printf("%d", BinarySearch(arr, 7, 6));
	return 0;
}

ps:1.通过main函数进行返参，将数组，数组长度，待查找数据给到BinarySearch函数中

2.通过BinarySearch函数数组，数组长度，待查找数据，左下标和右下标给BinarySearch0函数中

3.在BinarySearch0函数中进行递归结束条件是left>right或者arr[mid]=待查找数据

4.如果没有数据返回-1，如果找的数据返回数据的下标