x 的平方根

题目描述

实现计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例

输入: 4
输出: 2

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

解题思路

本题是典型的二分查找问题，故套用二分查找的模板，但是却有一些细节需要注意，优化前代码如下所示

public int mySqrt(int x) {
    int left=0;
    int right=x;

    while(right>=left){
        int mid=(left+right)/2;
        if(mid*mid == x){
            return mid;
        }else if(mid*mid < x){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return right;
}

优化

之前在写二分查找相关内容的时候，我就记录过int mid=(left+right)/2;这里最好写成int mid=(left+right) >>> 1;，因为这样可以有效防止整型溢出的问题，但是由于这个问题出现可能性不高，故没有引起重视，这次的上述代码中，mid*mid则就易出现溢出问题，故本文代码应该修改为如下所示

public int mySqrt(int x) {
    if(x == 0){
        return 0;
    }
    if(x == 1){
        return 1;
    }
    int left=0;
    int right=x;

    while(right>=left){
        int mid=(left+right) >>> 1;
        if(x/mid == mid){
            return mid;
        }else if(x/mid > mid){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return right;
}

因为将乘法改为了除法，解决了内存溢出问题，但是除法也应该相应的注意边界问题，以免x/mid中被除数mid的值为0