【C语言】二分查找

一. 二分查找基本思路

在有序表中，每次都取中间元素作为比较的对象。

如果给中间值与给定值相等，则查找成功，返回该元素的下标/索引；

如果中间值大于给定值，则在中间值的右半区间继续查找；

如果中间值小于给定值，则在中间值的左半区间继续查找；

确定了该元素所在范围那么范围外的元素就不需要查找了，不断重复上诉过程，直至找到

因为二分查找每次查找都可以剔除一半的查找范围，所以相比顺序查找每次一个一个元素查找，查找效率提高了很多。

二分查找需要两个必要条件：

1.数组元素必须有序

2.查找的数值不能多个，只能一个

二. 详细图解

例如：给定一个有序数组 nums = {1,2,4,5,7,8,11,15} 中，求数字7所在数组中的下标

二分查找过程：

（1）定义两个指针 left 和 right ；left 指向首元素的下标，right 指向最后一个元素的下标。 traget 为目标值。即：

（2）求中间元素的值mid，即：mid = left + (right - left) / 2 得到中间下标 通过中间下标可以访问到中间元素 nusm[mid] 。即：

问题：求中间值为什么不用 mid = (left + right) / 2 呢？

原因：如果是两个较大的值，相加超过了 int 取值范围(2147483647)就会导致溢出

（3）使用中间值 nums[mid] 和目标值 target 对比，此时 nums[mid] < target 就证明 nums[mid] 左边的值 和 nums[mid]的值都不需要继续对比了。然后将 left 指针移动到 mid+1 的位置，查找范围就是 [mid+1,right] 。即：

（4）继续对比，发现 nums[mid] > target。证明 nums[mid] 的值 和 nums[mid] 右边的值都不需要对比了。就让 right 指针移动到 mid-1的位置。即：

（5）现在 nums[mid] 和 target 相等，然后返回 mid ，查找结束

下面来看一道经典的二分查找例题，加深理解

三. 例题

题目：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

来源：力扣（LeetCode）

示例1：

输入：nums = [-1,0,3,5,9,12]，target = 9

输出：4

解释：9 出现在 nums 中并且下标为 4

示例2：

输入：nums=[-1,0,3,5,9,12]，target = 2

输出：-1

解释：2 不存在 nums 中因此返回 -1

1. 第一步

首先是在一个有序的数组中查找某个元素的，那就需要一个数组来存放一些 int 类型的数据，可以通过题目看到除了输入一个数组 nums 外，还需输入一个目标值 target

#include <stdio.h>
void main() {
    int nums[] = {-1,0,3,5,9,12};
    int numsSize = sizeof(nums) / sizeof(nums[0]);//数组大小
    int target= 0;//目标值target
    scanf("%d",&target);
}

2.第二步

写一个二分查找函数，并且定义两个指针 left 和 right，left 为首元素的下标，right 为最后一个元素的下标, 然后求中间元素的下标 mid ( mid = left + (right - left) / 2) 即：

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
    int left = 0;//首元素下标
    int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)

    //int mid = (left + right) / 2;//如果是两个较大的值超过了int类型的取值范围就会导致溢出
    int mid = left + (right - left) / 2;//中间元素的下标 防止溢出

}
void main() {
    int nums[] = {-1,0,3,5,9,12};
    int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
    int target= 0;//目标值target
    scanf("%d",&target);
    printf("%d", binarySearch(nums,numsSize, target));
}

3.第三步

使用中间元素和目标值(target)对比，假如target = 9，那么 中间元素(5) < 目标值(9)，中间元素左半部分的值及中间元素本身也就没有必要继续对比了，此时的查找范围为[mid+1,right]，也就是 left = mid + 1，right位置不变，即：

问题： 如果我们查找的值是小于中间元素的时候呢？

回答：当 目标值 < 中间元素 时，就代表目标值在中间元素的左半部分，右指针就需要移动，也就是right = mid - 1，left不需要移动，此时查找范围为：[left,mid-1]。

大于和小于的情况都判断了，还有相等的情况，目标值 == 中间元素 时，就意味着找到该元素了，直接返回该下标即可。代码如下：

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
    int left = 0;//首元素下标
    int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)

    int mid = left + (right - left) / 2;//中间元素的下标 防止溢出
    int numsMid = nums[mid];//中间元素
    //目标值大于中间元素时
    if (numsMid < target) {
        //查找范围：[mid+1,right]
        left = mid + 1;
    }
    //目标值小于中间元素时
    else if (target < numsMid) {
        //查找范围：[left,mid-1]
        right = mid - 1;
    }
    else return mid;//相等时直接返回该元素下标

}
void main() {
    int nums[] = {-1,0,3,5,9,12};
    int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
    int target = 0;//目标值target
    scanf("%d",&target);
    printf("%d", binarySearch(nums,numsSize, target));
}

4.第四步

最后就是重复执行上述过程了，每次都让目标值和中间元素对比，从而缩减查找范围，直至找到，如果没有的话返回-1

注意：

1.在查找元素时 left 和 right下标会越来越近甚至指向同一个下标，过程中 left 始终在 right 的左边（即：left <= right）。

2.如果一直找不到那个元素，两个下标必然会相互交错（即: left > right），这时循环结束。所以循环条件就是：while(left <= right)

最终代码：

#include <stdio.h>
int binarySearch(int nums[],int numsSize,int target) {
    int left = 0;//首元素下标
    int right = numsSize - 1;//末元素的下标(总长度-1,数组从0开始)
    
    while (left <= right) {
        int mid = left + (right - left) / 2;//中间元素的下标 防止溢出
        int numsMid = nums[mid];//中间元素
        //目标值大于中间元素时
        if (numsMid < target) {
            //查找范围：[mid+1,right]
            left = mid + 1;
        }
        //目标值小于中间元素时
        else if (target < numsMid) {
            //查找范围：[left,mid-1]
            right = mid - 1;
        }
        else return mid;//相等时直接返回该元素下标
    }
    return -1;//没有找到目标值,返回-1
}
void main() {
    int nums[] = {-1,0,3,5,9,12};
    int numsSize = sizeof(nums) / sizeof(nums[0]);//数组长度
    int target = 0;//目标值target
    scanf("%d",&target);
    printf("下标：%d", binarySearch(nums,numsSize, target));
}

运行结果：

5.总结

二分查找最重要的两个点，就是循环条件和后续的区间赋值问题

关于二分查找的讲解到这里就结束了，如果有什么不对的地方欢迎在评论区指正，谢谢支持~