可曾听闻二分查找？

引子

这里讲个我初中数学老师讲给我听的小故事，好久之前，湾湾做个一个综艺节目，上面有个挑战就是让参赛选手猜一个在一到一百之内的数字，你每猜一个数字，人家就会告诉你你猜大了还是小了，猜的次数越少，你获得的奖金也就越高。结果那个参赛选手很机灵啊，上来就猜五十，接着二十五，然后十二。
我觉得吧，就算让兄弟们上场多半也是会这样子，我相信兄弟们都是有慧根的人，其实如果我问你是怎么想到这样子做的，你多半是答不上来的，所以说思维是一种很奇妙的东西，你在不知不觉之中就运用到了一定的思维，就像我在刚开始学冒泡排序的时候，我根本不知道什么是算法，直到后来有人跟我讲解了一下算法的意思我才恍然大悟。
好，我有点扯远了，今天我们的重点就是向家人们介绍二分查找

细说二分查找

我关于二分查找的讲解就是基于我刚才讲的这个综艺，我们今天也上一把综艺，也搞一把！
首先我先敲一下黑板，记住记住，二分查找只适用于有序数列，升序降序我们不管，严格升序还是不严格降序我们也不管，但是我们要牢记有序二字，等到后面我i们开始刷题目的时候就会发现，一看到有序基本上就是这里的二分查找！
那我们首先先创建一个有序数组，这种时候我们就不用太老实了，一个个scanf输入这还了得啊？要知道赋值一样可以达到我们要的效果！

	int arr[100] = {0};
	for (int i = 0;i < 100;i++)
	{
		arr[i] = i + 1;
	}

emmm，这个时候数组已经创建好了，我们是不是要生成一个随机数，然后让我猜数字啊，由于这篇博客我们的重点就是讲解二分查找，所以阿涛在这里就不再过多的给你们开小灶了，我试试能不能在下一篇博客里面好好地给大家讲解一下创建随机数的那些事儿！这里我们就意思一下，选个十一吧，因为阿涛记得一个女生的网名就是十一，嘿嘿！！`

			int n = 0;
			int k = 11;
			scanf("%d", &n);

那现在我们来稍微盘一下逻辑哈，无非就是三种情况，大了，小了，中了！！如果中间的数字大于答案，说明答案在左边，如果中间的数字小于答案，说明答案在后边，如果中间的数字正正好是答案，那就皆大欢喜！

	if (mid > k)
	{
		printf("猜大了\n");
	}
	if (mid < k)
	{
		printf("猜小了\n");

	}
	else
	{
		printf("蒙对了\n");
	

那我们稍微思考一下，我们不可能有这么好的运气吧，一次就能够猜中，所以十分显然其中必然会有循环的存在。
那么现在我们就来模拟一下，输入50，程序告诉你猜大了，说明什么？答案在你的左边，也就说明连同五十在内右边的数字都不可能是答案了对不对？这种时候，谁再猜大于等于50的数字那不是和钱过不去吗？那接下来，很显然我们还是要接着进行二分查找，但是后边的范围就变了，将不再是100，而是49了，同理猜小了也是一个道理！不难写出下面代码的雏形：

while ()
	{
		scanf("%d",&n);

		if (mid > k)
		{
			printf("猜大了\n");
			right = n - 1;
		}
		else if (mid < k)
		{
			printf("猜小了\n");
			left = n + 1;

		}
		else
		{
			printf("蒙对了\n");

		}
	}

刚才在敲代码的时候我还发现了一个小错误，在第二种情况的时候我少加了一个else，加不加将会是天差地别，这点我在之前一篇博客里面提到了，有兴趣的小伙伴可以去看一看！！
那么接下来我们还要解决的问题就是mid，right，left，循环条件都是什么！
刚开始的时候很显然，left就是第一个数字的下标，也就是零，而right是可以通过sizeof/sizeof来求出来的（兄弟们想啊，总共的内存大小除以一个元素的内存大小可不就是数组元素的个数吗），解决了left，right，mid不是手到擒来的小事吗？（L+R）/2就成！

	int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	int mid = (right + left) / 2;

	while ()
	{
		scanf("%d",&n);
		mid = (right + left) / 2;
		if (arr[n-1] > k)
		{
			printf("猜大了\n");
			right = n - 1;
		}
		else if (arr[n-1] < k)
		{
			printf("猜小了\n");
			left = n + 1;

		}
		else
		{
			printf("蒙对了\n");

		}
	}

各位客官老爷听完了我的讲解，再看这串代码有没有一种豁然开朗的感觉？
当然了，上面的代码还比较落后需要通过各位客官老爷手动输入数字，还要计算中间值，忒麻烦了。我，我们是谁，我们可是不可一世的程序员，这点小事情还需要自己动手？开什么玩笑！

	while ()
	{
		mid = (right + left) / 2;
		if (arr[mid] > k)
		{
			right = mid- 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;

		}
		else
		{
			printf("答案为%d", arr[mid]);
			break;

		}
	}

现在就只差一个循环条件了，我们可以想象到，左边在一直往右边增大，右边一直往左边减小，如果一直找不到我们想要的数字，那么总有一天左边会跑到右边，对待这一段明知道不会有结果的关系，我们是不是应该及时止损，是不是应该急流勇退，然后开始我们新的生活？我们就应该潇洒地转身，然后留给过去一个帅气的背影，就应该及时退出循环，最好再打上一行字，告别过去！那么循环条件就是呼之欲出了，左边不能够大于后边！！！今天我刚好高兴，我还可以统计一下 总共循环了多少次！

int main()
{
	int k = 11;
	int arr[100] = {0};
	for (int i = 0;i < 100;i++)
	{
		arr[i] = i + 1;
	}
	int left = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	int right = sz - 1;
	int mid = (right + left) / 2;
	int count = 0;
	while (left<=right)
	{
		count++;
		mid = (right + left) / 2;
		if (arr[mid] > k)
		{
			right = mid- 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;

		}
		else
		{
			printf("找到了，答案为%d\n", arr[mid]);
			break;

		}
	}
	if (left > right)
	{
		printf("找不到你输入的数\n");
	}
	else
	{
		printf("count=%d", count);


	}
	return 0;
}

下面再给兄弟们看一下找不到的情况：

总结：

二分查找多运用于有序数列，二分查找也叫做折半查找，通过名字就很容易理解，重点要设置好循环的条件，中间还有一个设置随机数以及sizeof的运用，我先空着，接下来有时间一定给兄弟们补上！！！

希望我的这篇博客能够给予到兄弟们一些帮助！
百年大道，你我共勉！！！！