leetcode-剑指 Offer II 072. 求平方根【java】

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 4
输出: 2
示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

提示:

0 <= x <= 231 - 1

代码1：用Math函数

class Solution {
    public int mySqrt(int x) {
        double n=Math.sqrt((double)x);
        int s=Math.round((int)n);

        return s;
    }
}

代码2：二分查找

class Solution {
    public int mySqrt(int n) {
        int left=1;
        int right=n;
        while (left<=right)
        {
            int mid=(left+right)/2;
            if (mid<=n/mid)
            {
                if ((mid+1)>n/(mid+1))
                {
                    return mid;
                }

                left=mid+1;
            }
            else
                right=mid-1;
        }

        return 0;
    }
}