39题--找到x的平方根

1. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

第一种写法：按照数学公式做二分范围限制，理解起来比较困难

class Solution {
    public int mySqrt(int x) {
        /**
         思路1：暴力法
         （1）遍历1 - x的数字，求平方与x大小做对比
         （2）等于的时候，即为当前值，大于的时候，即为上一个值
         思路2：二分法
         （1）1-x这个范围内，对1-x做二分查找，如果一个数的平方大于x，说明这个数一定不是x的平方根
         （2）所以需要找到第一个平方小于等于x的数字
         （3）但是二分法有可能会出现找到第一个小于之后，实际结果在范围之外，所以当出现小于等于的时候，
         右移左指针，再此执行二分操作
         （4）当l=r的时候即为找到了结果
         */
        if(x == 0 ){
            return 0;
        }
        if(x == 1){
            return 1;
        }
       int left = 1;
       int right = x / 2;
        // 在区间 [left..right] 查找目标元素
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            // 注意：这里为了避免乘法溢出，改用除法
            if (mid > x / mid) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            }
        }
        return left;
    }
}

第二种写法：正常思路的二分法，按照1……x这个范围进行二分

class Solution {
    // 上面的写法不是很好理解，再来一种新写法
    // 第二种写法
    public int mySqrt(int x){
        if(x == 0 ){
            return 0;
        }
        int left=1;
        int right = x,ans = -1;
        // 这里小于等于，是考虑x=1这种场景
        while(left <= right){
            // 正常来说这么写没问题，但是如果x是byte类型，那么范围是125 - 127，如果相加除以2会出现溢出
            // int mid = (left + right) / 2;
            // 因此换成下列写法
            int mid = left + (right - left)/2;
            // 除法代替乘法，同样是为了防止溢出
            // 当mid大于x/mid说明，mid比平方根大
            if(mid > x / mid){
                right = mid-1;
            }else{
                left = mid+1;
                ans = mid;
            }
        }
        return ans;
    }
}