目录
问题
在一个有序数组中查找具体的某个数字n
比如我买了一双鞋，你好奇问我多少钱，我说不超过300元。你还是好奇，你想知道到底多少，我就让你猜，你会怎么猜？
答案：你每次猜中间数
思路
我们先定义一组有序数组，假设为：int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
因为我们知道数组的下标是从0开始的，假设我要找数字7的下标
来看一张图：
数字1的下标是0，数字10的下标是9
我们先求中间元素：(0+9) / 2 = 4 （注意：这里的\是不取余的），那么得到了下标为4的数字5
而数字5要比我们找的7小，说明我们在数字5的左边是找不到的。
所以我们查找的范围缩小为是：数字6~10，是不是我们的范围缩小了一半？
那么这个新的范围我们是怎么查找的呢？
其实很简单，如图，这是新的范围，右下标还是9，而左下标就变成了：4+1=5
而左下标5对应的就是数字6，右下标9对应的是数字10
我还是先求中间元素：(5+9) / 2 = 7，那么7作为下标的话，对应的数字就是8
而数字8比我要找的数字7大，说明我们要找的下标在数字8的左边
所以我们被查找的范围缩小为：数字6~7，那么我的查找范围是不是又相当于缩小了一半？
那么我们就可以得到了一个新的范围：如图，左下标还是5，而右下标就变成了：7-1=6
此时左下标5对应的是数字6，右下标6对应的数字7，那么中间元素为：(5+6) / 2 = 5
这里我们得到了中间元素为5，进而锁定的数字就是6
而数字6比我要找的数字7小，说明我要找的元素在数字6的右边，而在数字6的右边，查找的范围只剩一个数字7了
那么数字7的左下标就为6，右下标还是为6
那么我现在还是通过下标的计算方法：(6+6) / 2 = 6，那么6锁定的元素就是我们的数字7
数字7和我们要找的7对比了一下，相等！那么说明已经找到了
这就是二分查找的过程！
详解
我刚刚查找的过程中，你会发现，我每次都在找{ 1,2,3,4,5,6,7,8,9,10 }的中间元素
中间元素比我要找的元素小，说明我要找到元素在中间元素的右边，那么范围就缩小了一半
这种思路，每一次范围都在缩小一半，查一次缩小一半
这种算法就叫做：折半查找或者二分查找
代码
在下面的代码中
int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10 }; //计算数组元素的方法： int sz = sizeof(arr) / sizeof(arr[0]); //sizeof(arr)计算的是数组的总大小，单位是字节，这组数组是10个元素，每个元素是int类型 //所以总大小为40 //sizeof(arr[0])就是计算第一个元素的大小，第一个元素的大小为1个int，也就是4个字节 //40 / 4 = 10 int k = 7; //我们要查找的数字 int left = 0;//定义左下标 int right = sz - 1; //(元素 - 1)就为右下标 while (left <= right) { int mid = (left + right) / 2; //mid定义中间元素 if (arr[mid] < k) { left = mid + 1; } else if (arr[mid] > k) { right = mid - 1; } else { printf("找到了,下标是:%d\n", mid); break; //找到了就停下来 } } //当左下标>右下标时，是找不到的 if (left > right) { printf("找不到\n"); } return 0; }
代码执行的结果：
