CC53.【C++ Cont】二分查找的普通模版

zhangcoder

已于 2025-05-13 10:36:05 修改

阅读量769

点赞数 8

分类专栏： # 二分法 LeetCode题解 C++ Contest 文章标签： c++ 开发语言 leetcode 二分法

于 2025-05-12 10:09:35 首次发布

本文链接：https://blog.csdn.net/2401_85828611/article/details/147858881

版权

C++ Contest 同时被 3 个专栏收录

74 篇文章

订阅专栏

LeetCode题解

55 篇文章

订阅专栏

二分法

1 篇文章

订阅专栏

以LeetCode上的一道题为例:704. 二分查找

分析

引入二段性:分两段,舍一段,操作另一段(这个是二分查找的本质!)

1.知识回顾

之前在C语言专栏中的文章提到了二分查找,可复习:

E7.【C语言】练习：在一个有序数组中查找具体的某个数字n（二分查找）

本文将提炼出一些关键点

2.关键点

特点

算法细节较多,一一介绍:

之前讲过二分查找的前提: 数组有序时才能使用二分查找,其实并不是这样!,

当数组满足某特定规律时,也可以使用二分查找(这个后面会介绍)

三个模版

有以下二分查找的固定格式,做题只需要照葫芦画瓢,注意先理解再记忆

普通的模版(有局限)

以LeetCode上的一道题为例:704. 二分查找

https://leetcode.cn/problems/binary-search/description/

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 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
提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

分析

暴力解法直接从左向右或从右向左找,这里不写,讲讲暴力解法的缺陷:每次只能比较一个数,时间复杂度为 $O(N)$

注意到题目条件"一个 n 个元素有序的（升序）整型数组 nums ",那么可以利用数组的单调性对暴力解法优化

以nums = [-1,0,3,5,9,12], target = 9为例说明,现查找到3,发现target>3且数组单增,那么3的左侧是不需要查找的,继续查找3的右侧

引入二段性:分两段,舍一段,操作另一段(这个是二分查找的本质!)

对于上述单增数组有许多分段方式:

1.二分

即近似分成二等分

2.三分

将数组近似分成三等分

然后任意选一个节点来分段,例如:

3.四分

将数组近似分成四等分......

......

当然也可以使用随机数来分段

其中二分的时间复杂度是最低的,时间复杂度为 $O(logN)$ ,当然某些情况下使用随机数来分段时间复杂度也比较低

算法:设数组是单调递增的,对它平分两段:

比较nums[mid]和num[target]的大小,

1.nums[mid]==num[target],结束循环,返回结果

2.nums[mid] $<$ num[target],依据二段性:分两段,舍一段,操作另一段

,舍弃[left,mid]段,去[mid,right]段寻找,那么更新left
left=mid+1;//right不变
nums[mid] $>$ num[target],返回结果,依据二段性:分两段,舍一段,操作另一段

,舍弃[mid,right]段,去[left,mid]段,那么更新right
right=mid-1;//left不变
3.更新mid(有多种方法,上面提过了)

只需要循环上面三步,变化寻找的区间,最终一定可以找到结果

结束循环的两个条件:

1.nums[mid]==num[target],直接返回结果

2.left $>$ right,(注:left==right,分的段是一个"点",只有一个元素,但也需要判断是否等于target,仍然需要循环),没有找到target

那么循环的条件是:left $\leqslant$ right

代码

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid=left+(right-left+1)/2;
            if (nums[mid]==target)
                return mid;
            if (nums[mid]>target)
                right=mid-1;
            if (nums[mid]<target)
                left=mid+1;  
        }
        return -1;//没找到target
    }
};

注:mid不要写成(left+right)/2!之前在L42.【LeetCode题解】四数之和(双指针思想) 从汇编角度分析报错原因文章提到过报错的原因,当数组过长时,加法可能导致溢出

防溢出的方法:(left+right)/2改为left+(right-left)/2或left+(right-left+1)/2

提交结果

同理三分法只需要将除数2改成3即可,四分法、五分法同理

mid=left+(right-left+1)/3;

当然也可以使用随机数来分两段

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        srand((unsigned int)time(nullptr));
        int left=0;
        int right=nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid=left+rand()%(right - left + 1);
            if (nums[mid]==target)
                return mid;
            if (nums[mid]>target)
                right=mid-1;
            if (nums[mid]<target)
                left=mid+1;   
        }
        return -1;
    }
};

注: 循环体中,如果最后更新mid将导致除0错误!

这样写是错误的:

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        srand((unsigned int)time(nullptr));
        int left=0;
        int right=nums.size()-1;
        int mid=left+rand()%(right - left + 1);
        while(left<=right)
        {
           
            if (nums[mid]==target)
                return mid;
            if (nums[mid]>target)
                right=mid-1;
            if (nums[mid]<target)
                left=mid+1;
            mid=left+rand()%(right - left + 1);   
        }
        return -1;
    }
};

排查错误:

VS中进入调试模式

发生错误的地方是: mid = left + rand() % (right - left + 1),则mid=2+rand()%(1-2+1)=2+rand()%0,为除0错误,此时left仍然<=right,策略:先更新mid的值,这样进行if判断时能修改left和right的值,能及时退出循环,防止除0错误

提交结果:

普通模版总结

利用二段性填以下模版空缺的地方:

while(left<=right)
{
    int mid=left+(right-left+1)/2;
    if (......)
        return mid;
    if (......)
        right=mid-1;
    if (......)
        left=mid+1;  
}

注意1.判断条件 2.mid防溢出方法 3.left和right的更新方式

其他两个模版见下一篇文章