【手绘漫画】图解LeetCode之x 的平方根（LeetCode 69题）

Myth丶恋晨 2023-07-24 14:41 6阅读 0赞

![在这里插入图片描述][20200412160528409.gif]

### 文章目录 ###

*  图解LeetCode刷题计划
 *   *  1、写在前面
     *  2、题目
     *  3、正文
     *  4、代码

# 图解LeetCode刷题计划 #

## 1、写在前面 ##

手绘漫画系列正式上线！！！“图解LeetCode刷题计划” 来了！！！

今天是第七期，争取每天一期，最多两天一期，欢迎大家监督我。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]  
最近依旧是二分查找算法呢~

使用新版的模板加上图解，相信你能更加理解二分法的使用！！！  
![在这里插入图片描述][20200331223510788.png]

## 2、题目 ##

首先看一下题目，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]  
分界条件就是我们的 `mid * mid` 和 `x` 的关系！！！  
![在这里插入图片描述][20200331223457291.png]  
![在这里插入图片描述][2020040522155962.png]

## 3、正文 ##

首先分析一下情况，

确定一下 `left` 和 `right`，然后编写二分查找模板。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]  
可以看到，`mid * mid <= x` 时，所以 `target` 在 `mid` 的右侧，因为有等号，所以 `left = mid`，`mid * mid <= x` 这么写不好，容易溢出，所以可以写成 `mid<=x/mid`。

因为是模板二，所以不要忘记给 `mid` 加1！！！  
![在这里插入图片描述][20200331223448439.png]

## 4、代码 ##

int mySqrt(int x){ 
        int left=0;
        int right=x;
        while(left<right){ 
            int mid=(long)left+right+1>>1;
            if(mid<=x/mid){ 
                left=mid;
            }
            else{ 
                right=mid-1;
            }
        }
        return left;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][2020033119171520.png]

> **如果有幸帮到你，请帮我点个【赞】，给个【关注】！如果能顺带【评论】给个鼓励，我将不胜感激。**

***如果想要更多的资源，欢迎关注 @我是管小亮，文字强迫症MAX~***

[20200412160528409.gif]: /images/20230528/e08e70087f2f492bba72742bf4ebafae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70]: /images/20230528/587a83df2fc642e1afceffa9e87a60d6.png
[20200331223510788.png]: /images/20230528/8d18a63c42b44969a708ebcc61be126c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 1]: /images/20230528/a2e10469f0e748c48641352e78c9e435.png
[20200331223457291.png]: /images/20230528/9b14b926c80144559f3843f369de4319.png
[2020040522155962.png]: /images/20230528/6795c035982048bfb7ad9a77368fe86b.png?
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 2]: /images/20230528/07acdd42718047a39268cfc592472040.png
[20200331223448439.png]: /images/20230528/ceb2a5461b9844339a42423aaca1dee0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RlRnVpcm5ldmVy_size_16_color_FFFFFF_t_70 3]: /images/20230528/9c466dc6ee5c47b78c9edb904628d9c9.png
[2020033119171520.png]: /images/20230528/01c7d8ae95144140becb13c4bddd255a.png