引入

? ? 这里我给大家一个有序数组，要在这个数组中找到指定的元素。

例：在下面数组中找到‘7’，并返回其下标。

int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };

? ?方法会有很多，我的第一反应的想法如下：

#include<stdio.h>
int main()
{
	int i = 0;
	int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };
	int k = 7;
	for (i = 0; i < 11; i++)
	{
		if (arr[i] == k)
			printf("找到了，下标是%d\n", i);
	}
	if (i == 11)
		printf("没找到");
    return 0;
}

? 上面代码的思路就是遍历数组，一个一个查找。当然这种方法是肯定可行的。但是，当这个数组有较多数据时，我们就会发先，查找起来效率很低。因为这里是一个有序的数组，这就给了我们很大的发挥空间，因而我们就可以使用二分查找（折半查找），可大大提高效率。

接下来我给大家仔细解释一下二分查找。?

一、二分查找的简单解释

? 二分查找也算是一个非常简单的算法了，也是我们必须要掌握的一个算法。那么二分查找是什么呢？二分查找的思路是什么呢？

? 二分查找又叫折半查找，是应用在一个有序数组中的一个高效率查找的方法。这里要注意的是，二分查找前提是必须是有序的数组。

?二、二分查找的思路解析

1、二分查找的思路描述

? ? 因为是有序的数组，我们就可以直接用数组中间的元素来和你要查找的元素进行比较。如果中间的元素比你要查找的元素大，我们就可以直接舍去数组的后半部分，定位到数组前半部分。同样，如果中间的元素比你要查找的元素小，我们就可以直接舍去数组的前半部分，定位到数组后半部分。在剩下的数据中我们再次重复上面的操作，当中间的元素等于你要查找的元素时，就找到了。我们发现，每次查找都会舍去现有的一半数据，相对遍历数组查找大大提高了效率。

? 中间元素的查找方法就是mid=（左元素下标 +右元素下标）/2。如果中间的元素比你要查找的元素大，我们怎么来到前半部分呢？很简单，左素下标不用变，我们只需要将右元素的下标改成中间元素下标减去一即可。如果中间的元素比你要查找的元素小，我们怎么来到半后部分呢？右元素下标不用变，左下标变成中间元素下标加一。

? 那要是查找的元素不存在呢？就上面的图我们来解释一下。假设我们要找的元素是6.5，?当进行到第三步时，我们就会只剩下‘7’这个元素。这时左下标是等于右下标的。但是中间的元素和要查找的元素并不相等，其实这是中间元素还是本身，但还需要再次查找比较，中间的元素比你要查找的元素大，右元素下标要减一。我发现，左元素下标大于了右元素下标，因为是有序的，这就意味着找不到了。

? 下面我们结合着代码综合理解一下。

2、二分查找的代码实现

#include<stdio.h>
int main()
{
	int i = 0, k = 0;
	int arr[] = { 0,1,2,3,4,5,6,7,8,9,10 };
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0])-1;
	printf("请输入你要查找的数:>");
	scanf("%d", &k);
	while (left<=right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下标是%d", mid);
			break;
		}
	}
	if (left > right)
		printf("没找到");
	return 0;
}