二分查找法的区间判断【C语言】网站首页 技术杂谈

二分查找法的区间判断【C语言】

七月巫山晴 2023-07-06 19:13:41

简介二分查找法的区间判断【C语言】

📢 ：二分查找法的区间判断

📢 ：当我们在写二分查找的题目的时候（这里以leetcode的704. 二分查找，为例），常常会因为区间的选择而疑惑，是应该选择 while(left < right)；,还是while(left <= right);,应该写成lright = mid;,还是right = mid - 1;

答案是都可以，这分别是区间的左闭右闭还是左闭右开，

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d2OMgaDP-1682906424642)(F:比特就业课Git仓库leetcode-quizzes1682872629451.png)]

上面是LeetCode上的题目，以下也是围绕着这道题来讲述的：

一，✨左闭右闭：

左闭右闭的意思是说我们判断的有序数组的区间，如果设数组长度为numsSize，定义：
```
int left = 0;
int right = numSize - 1;
```

那就说我们判断的区间是[left , right]。

接下来的代码是：
```
while (left <= right)
{
}
```
如何判断写 **<还是<=**呢？

我们思考一下边界情况，当数组为： [1],此时 left = 0 , right = 0 ,此时还需要进入循环（原因参考完整代码，不进入循环只能返回-1或者需要单独解决这种情况），所以可以有 left = right这种情况。

接下来的代码是：

 while (left <= right)
    {
        int mid = left + (right - left) / 2 ;
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else 
        {
            return mid;
        }

    }

当nums[mid] < taeget时，说明正确的目标值所在的区间是右半部分，由于nums[mid] != taeget;

所以下一次的搜索范围应该不包含nums[mid]，所以 left = mid + 1;

right = mid - 1的原因同上；

左闭右闭的完整代码如下；

int search(int* nums, int numsSize, int target){
    int left = 0 ;
    int right = numsSize - 1 ;
    while (left <= right)
    {
        int mid = left + (right - left) / 2 ;
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else 
        {
            return mid;
        }
    }
    return -1;
}

二，✨左闭右开

左闭右开的区间为 [left , right ),不包括right ,代码和左闭右闭也会有所不同，定义如下：

int left = 0;
int right = numsSize;

因为不包含right，所以right = numsSize; 而不是： right = numsSize - 1 ;

接下来的代码是：

while (left < right)
{
}

同上，我们假设数组为 [1] , 此时left = 0; right = 1; 此时已经到达了边界，但是left不会等于right了，所以代码为：left < right;

接下来的代码是：

    while (left < right)
    {
        int mid = left + (right - left) / 2 ;
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target)
        {
            right = mid ;
        }
        else 
        {
            return mid;
        }
    }

left 取值的原因同上；
当 nums[mid] > target ，包含目标值的范围在区间的左边，nums[mid]肯定不是目标值了，所以得取mid - 1

因为为左闭右开，右边的right不包含，所以使得right = mid；也就相当于使得mid-1在下一次搜索范围里了。

完整代码如下：

int search(int* nums, int numsSize, int target){
    int left = 0 ;
    int right = numsSize  ;
    while (left < right)
    {
        int mid = left + (right - left) / 2 ;
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target)
        {
            right = mid ;
        }
        else 
        {
            return mid;
        }
    }
    return -1;
}