题目描述

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。 正数的平方根有两个，只输出其中的正数平方根。 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例1

输入

8

返回值

2

解释：8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

思路 & 解答

这道题其实就是不断遍历，如果 m²<n, 而且 （m+1）²>n，那么说明m是n的平方根。

遍历的话，太慢，于是我们想到二分，不断缩小查找范围。

public class Solution72 {
    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;
    }
}

C++ 代码如下：

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;
    }
};

• 时间复杂度：O(logn)
• 空间复杂度：O(1)