【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找---day3

蔚落 2023-09-23 22:53 36阅读 0赞

![在这里插入图片描述][b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]

>  *  **博主简介：努力学习的预备程序媛一枚~**
>  *  **博主主页： [@是瑶瑶子啦][Link 1]**
>  *  **所属专栏: [LeetCode每日一题–进击大厂][LeetCode]**

![在这里插入图片描述][27e1a188f4e443c1bf6c992d149a4b9d.png_pic_center]

### 目录 ###

*  题目描述
 *  题目分析：
 *  代码分析：

# 题目描述 #

链接: [69. x 的平方根/Sqrt(x) ][69. x _Sqrt_x_]

> 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。  
> 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。  
> 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x \*\* 0.5 。

# 题目分析： #

*  **题型：二分查找目标元素**
 *  **关键：** 
    
     *  二分查找的的关键、易错（避免死循环）均在[【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一个位置|二分求下标][Leetcode_34.]、[【Leetcode每日一题】35.搜素插入位置|二分查找数组下标][Leetcode_35.]两篇文章中详细讲到，这里不重复造轮子
     *  ⭐本题关键突破：二分查找区间：\[0,x/2\]。`x/2>=根号x`(只有x=0,和x=1特殊)/**`mid^2<=left,left=mid;`—通过区间缩进，left不断逼近根号x（left^2<=x)**
     *  注意最后答案（这里记为ans)：`ans*ans<=x`(ans为整数）(本质类似于34题中的：**求第一个等于target的元素**，所用代码模板也是如出一辙）

# 代码分析： #

❌错误代码分析：（2023/1/25）

class Solution {
        
        public int mySqrt(int x) {
        
            //特例判断，因为x/2>=根号x，在x>=2的时候成立
            if (x == 0) {
        
                return 0;
            } else if (x == 1) {
        
                return 1;
            }
    
            int left = 0;
            int right = x / 2;
            while (left < right) {
        
                int mid = left + (right - left + 1) / 2;//防止溢出
    
                if (mid * mid <= x) {
        
                    left = mid;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

*  2023/1/25：因为没有考虑**乘法溢出：`mid*mid<=x`**，当mid过大时乘法溢出。（一开始还忘记了在`mid = left+(right-left+1);`中的`+1`，导致了死循环，实在不该，谨记判断是否+1就看**只剩两个元素时，mid的取值和区间划分能否缩小区间？若不能，必定死循环**
 *  ![在这里插入图片描述][ce43340d7d23401fb2967f2154afbbd2.png]

--------------------

✅正确代码：

class Solution {
        
        public int mySqrt(int x) {
        
            //特例判断，因为x/2>=根号x，在x>=2的时候成立
            if (x == 0) {
        
                return 0;
            } else if (x == 1) {
        
                return 1;
            }
    
            int left = 0;
            int right = x / 2;
            while (left < right) {
        
                int mid = left + (right - left + 1) / 2;//防止加法溢出
                if (mid <= x / mid) {
        //防止乘法溢出
                    left = mid;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

--------------------

> **write in the end:**
> 
>  *  **二分法系列题目：  
>     [【Leetcode每日一题】34.在排序数组中查找元素的第一个和最后一 个位置|二分求下标][Leetcode_34.]  
>     [【Leetcode每日一题】35.搜素插入位置|二分查找数组下标][Leetcode_35.]**
>  *  **建立此专栏的初衷是为了监督自己每天认真刷一个题，积少成多。并把自己每次刷题的思路、收获以博文的形式分享出来，帮助更多人，以及方便后续复习。如果有兴趣的同学可以订阅此专栏，我们一起刷题，一起交流，进步和学习！**[专栏：LeetCode每日一题–进击大厂][LeetCode 1]

![在这里插入图片描述][456fe14b32044d3083bc25853cf0ced7.gif_pic_center]

[b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center]: https://img-blog.csdnimg.cn/b88c49c5b7e04dacaaed7cf2fc928687.gif#pic_center
[Link 1]: https://blog.csdn.net/Yaoyao2024?spm=1011.2559.3001.5343
[LeetCode]: https://blog.csdn.net/yaoyao2024/category_12115665.html?spm=1001.2014.3001.5482
[27e1a188f4e443c1bf6c992d149a4b9d.png_pic_center]: https://img-blog.csdnimg.cn/27e1a188f4e443c1bf6c992d149a4b9d.png#pic_center
[69. x _Sqrt_x_]: https://leetcode.cn/problems/sqrtx/
[Leetcode_34.]: https://blog.csdn.net/Yaoyao2024/article/details/128758800?spm=1001.2014.3001.5501
[Leetcode_35.]: https://blog.csdn.net/Yaoyao2024/article/details/128750939
[ce43340d7d23401fb2967f2154afbbd2.png]: https://img-blog.csdnimg.cn/ce43340d7d23401fb2967f2154afbbd2.png
[LeetCode 1]: https://blog.csdn.net/yaoyao2024/category_12115665.html
[456fe14b32044d3083bc25853cf0ced7.gif_pic_center]: https://img-blog.csdnimg.cn/456fe14b32044d3083bc25853cf0ced7.gif#pic_center