算法萌新闯力扣：x的平方根

力扣热题：69.x的平方根

开篇

这是一道练习二分查找的题目，简单但也有一些细节需要注意，如判断条件、溢出等。

题目链接:69.x的平方根

题目描述

在这里插入图片描述

代码思路

1.一开始使用暴力解，发现超时了，看了标签，原来又是二分查找，做题太少了，敏感度有点差
2.知道是二分查找后，题目就非常好办了，只要你知道输出的数是如何判断就能解出：当前数的平方大于等于x，当前数加1的平方小于x

代码纯享版

class Solution {
    public int mySqrt(int x) {
        long low = 0, high = (long)x;
        while(low <= high){
            long mid = (low + high) / 2;
            if(mid * mid <= (long)x && (mid + 1) * (mid + 1) > (long)x) return (int)mid;
            else if(mid * mid > (long)x) high = mid - 1;
            else low = mid + 1;
        }
        return 0;
    }
}

代码逐行解析版

class Solution {
    public int mySqrt(int x) {
        long low = 0, high = (long)x; //利用二分查找来搜索目标值，查找过程中两数相乘可能会发生溢出，所以直接全部先变成long型。
        while(low <= high){
            long mid = (low + high) / 2; //二分查找的中间值
            if(mid * mid <= (long)x && (mid + 1) * (mid + 1) > (long)x) return (int)mid; //符合情况的mid值直接返回
            else if(mid * mid > (long)x) high = mid - 1; //根据二分查找的模版套入
            else low = mid + 1;
        }
        return 0; //无意义，单纯为了满足函数的规范
    }
}