详解【C语言】中的二分查找法和折半查找法（例题解答）

问题

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