C语言 二分查找

• 一、什么是二分查找？
• 二、二分查找的具体例子

二分查找的概念：当给到一组有顺序的数据时，需要查找一个数，是否在这组数据里面时，使用二分查找，通过这一组数据的两个数，确定一个范围，再根据这两个数，找到这个范围的中间值，使中间值与需要查找的那个数进行比较大小，若中间值<需要查找的数，则表示中间值左边的数据统统可以舍弃，因为需要查找的数，不在中间值的左边；若中间值>需要查找的数，则表示查找的数在中间值的左边，中间值右边的数，可以全部舍弃。不断的进行上述操作，确定范围，找到中间值，与需要的数进行比较，不断的舍弃左边或者右边的数，大大提高效率。

可以类比于： A买了一双鞋，价格为300，让B猜价格。
第一种方法：从1到300，一个一个的猜（效率低）。
第二种方法：选取中间值：150，A说猜低了，则1-150的数就不用猜了，大大加快了效率，则在选取150-300的中间值：225，重复第一步的操作，直到成功的猜对价格。

现在我理解到，在计算机中写程序，只是为了解决我们生活中的问题，而为了能够成功的写出程序，就要理解计算机的思维，成功转化为计算机的语言，所以就需要锻炼我们的编程思维。

编写代码在一个整形有序数组中查找具体的某个数

首先，先用自己的话，讲述一遍流程：
通过元素的下标，找到中间元素，使中间元素和需要查找的值进行比较大小，若小于，说明需要查找的值，在右边，则舍弃左边，若大于，说明需要查找的值在左边，舍弃右边。
接着使用计算机语言描述：
1：通过元素的下标，找到中间元素

#include
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	int left = 0;
	int right = sz - 1;
	int mid = (left + right) / 2;
	return 0;
}

2：使中间元素和需要查找的值进行比较大小，若小于，说明需要查找的值，在右边，则舍弃左边，若大于，说明需要查找的值在左边，舍弃右边。

#include
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	int left = 0;
	int right = sz - 1;
	int num = 7;
	int mid = (left + right) / 2;
	if (arr[mid] < num)
	{
		// 舍弃中间值左边的数据，左边元素的下标需重新设置,
		//为何要加1，想象猜鞋子的价格，刚开始猜150，猜小了，
		//1-150，就舍弃了，从151到300中选平均值。150到151，就要去加1.
		left = mid + 1;
	}
	else if (arr[mid] > num)
	{
		//舍弃中间值右边的数据，右边元素的下标需重新设置,
		//为何要减1，想上面猜鞋子的价格，如果刚开始猜150，猜大了，
		//150-300，就舍弃了，从1到149中选平均值。150->149，就要去减1.
		right = mid - 1;
	}
	else
	{
		printf("找到了，下标是:%d", mid);
	}
	return 0;
}

3：然后我们现在去想，这只是一次检验，那检测失败之后呢，left或者right被修改了，又如何进行下一次检验呢，所以我们可以想到使用while循环或者for循环语句。

完整代码实现：

#include
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	int left = 0;
	int right = sz - 1;
	int num = 7;
	// 此时的while循环的条件是left<=right，为什么是这个？
	//我们想，使用二分查找的根本目的是什么？是查找一个数，
	// 所以这是使用while循环的目的，当数据还没有遍历完，就不能停止循环，
	//如何表明数据没有遍历完，左右两个下标是表示一个范围，有范围就代表有数据，如果范围不存在了，自然数据就遍历完了
	//范围存在时，左边元素的下标是小于等于右边元素的下标，左右两个下标相当时代表此时只剩一个值了。
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < num)
		{
			// 舍弃中间值左边的数据，左边元素的下标需重新设置,
			//为何要加1，想象猜鞋子的价格，刚开始猜150，猜小了，
			//1-150，就舍弃了，从151到300中选平均值。150到151，就要去加1.
			left = mid + 1;
		}
		else if (arr[mid] > num)
		{
			//舍弃中间值右边的数据，右边元素的下标需重新设置,
			//为何要减1，想上面猜鞋子的价格，如果刚开始猜150，猜大了，
			//150-300，就舍弃了，从1到149中选平均值。150->149，就要去减1.
			right = mid - 1;
		}
		else
		{
			printf("找到了，下标是:%d", mid);
			// 找到了之后，就退出while循环。
			break;
		}
	}
	if (left > right)
	{
		printf("没有找到");
	}
	return 0;
}