引入
这里我给大家一个有序数组，要在这个数组中找到指定的元素。
例：在下面数组中找到‘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; }
上面的代码中，要查找的数改成自己输入了。但是二分查找的思路是没变的。
总结
- 二分查找应用在有序数组中；
- 重点理解二分查找的思路；
- 掌握二分查找代码的实现。
