题目描述

题目链接

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

1
2
3
4
示例 1：

输入：x = 4
输出：2
1
2
3
4
5
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

算法1

(暴力枚举) O(n)O(n)

可以从大到小枚举 小于 x 的数字 i， 直到 i * i 小于等于 x 为止，即为我们的要找的答案

但是这种枚举的方式当 x 很大时，容易超时，因此需要进一步优化

(二分查找) O(logn)O(logn)

可以考虑单调性，由于从 1 ~ x ，所有的数字都是递增的，因此他们的平方也是递增的，所以具有单调性，可以使用二分查找的方式每次缩小一半的查找方式，因此可以达到 O(logn)O(logn) 的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = INT_MAX;

        while( l < r)
        {
            long long mid = (long long)l + r + 1>> 1;
            if( (long long) mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};