问题

在一个有序数组中查找具体的某个数字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 = 10int 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;
}

代码执行的结果：