69.Sqrt(x)

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

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

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

示例 1：

1
2
输入：x = 4
输出：2

Solution

和367 有效的完全平方数一样，都是二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    // mySqrt方法接受一个整型参数x，并返回x的平方根的整数部分
    public int mySqrt(int x) {
        // 初始化二分查找的左边界l为0，右边界r为x，答案ans初始化为-1
        int l = 0, r = x, ans = -1;
        // 当左边界不大于右边界时，执行循环
        while (l <= r) {
            // 计算中间值mid，防止(l+r)直接相加造成的整型溢出
            int mid = l + (r - l) / 2;
            // 如果mid的平方小于等于x，那么mid可能是我们要找的答案
            // 将mid赋值给ans，并将左边界移动到mid+1，继续在右半边寻找可能的更大值
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                // 如果mid的平方大于x，说明答案在左半边
                // 将右边界移动到mid-1
                r = mid - 1;
            }
        }
        // 循环结束后，ans中存储的是x的平方根的整数部分
        return ans;
    }
}