69. x 的平方根

分析

首先我们要清楚 x 的算术平方根是什么，如果 n*n <= x 同时 (n+1)*(n+1) > x 那么 n 就是 x 的算数平方根。
这里有一点需要注意，算术平方根是不需要满足 n = x/n 的，比如 2*2 <= 8 而且 3*3 > 8 所以 2 就是 8 的算数平方根，但是 8/2=4
这个跟 367. 有效的完全平方数是不一样的，我们判断完全平方数的标准是存在正整数 n，且 n 满足 n=x/n 且 0 =x%n。这是两个完全不一样的逻辑。

具体思路就是
直接在 0 和 x 之间进行二分查找即可。
有三点需要注意

首先判断目标值为 0 或者 1 的时候，都可以直接返回 x
mid*mid 的时候可能会超过 int 类型的最大值，官方答案里是通过进行类型转化来解决这个问题（转化为 long 型），有一种更巧妙的办法是用 mid > target/mid 来进行比较，很巧妙。
mid*mid > target 的时候，说明 mid 大了，缩减右区间为 mid-1 ， mid*mid <= target 的时候，其实 mid 的值可能就是我们的目标值，但是根据二分法的定义，查找区间此时要缩小 start = mid +1，因此为了不破坏二分法的定义，此时我们只能用另外一个单独的变量来保存结果 mid，这个思路其实跟 34. 在排序数组中查找元素的第一个和最后一个位置一样，需要从左侧逼近最大的正整数平方根，常规的二分法有三个变量，查询区间 [start,end] 和区间中间索引值 mid，但是查找 x 的平方根的二分法有第四个变量，最终平方根 result。此时的二分法只是用于快速遍历。
经过二分法最终返回的是最接近的正整数吗？这个问题其实我们在 34. 在排序数组中查找元素的第一个和最后一个位置中也思考过了，不会。

解法

public int mySqrt(int x) {
    if(x==0){
        return 0;
    }
    int start=1,end=x;
    int result=1;
    while(start<=end){
        int mid  = start + (end-start)/2;
        // 避免mid超长
        if(mid > x/mid){
            end = mid-1;
        } else {
            // 用一个专门的值来保存值，不要轻易修改二分法的定义
            start = mid+1;
            // mid实际上就是我们要找的值
            // 假设题目要求我们返回平方大于x的第一个整数，那这里就应该把mid+1即start赋值给result
            result = mid;
        }
    }
    return result;
}

69. x 的平方根

分析

解法

相关题