69. Sqrt(x)#

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

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

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

7

8

9
示例 1：
10

11
输入：x = 4
12
输出：2
13
示例 2：
14

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

19

20
提示：
21

22
0 <= x <= 2^31 - 1

1
class Solution {
2
public:
3
    int mySqrt(int x) {
4
        long long l = 0, r = x;
5
        while(l < r)
6
        {
7
            long long mid = (l + r + 1) >> 1;
8
            if(mid <= x /mid) l = mid;
9
            else r = mid - 1;
10
        }
11
        return l;
12
    }
13
};