69. x 的平方根

分析

有三点需要注意

首先判断目标值为 0 的情况
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 = mid;
        }
    }
    return result;
}

69. x 的平方根

分析

解法

相关题