69. x 的平方根

发表于 更新于

难度系数： 简单

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

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

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

示例 1:

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

示例 2:

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

提示：

  • 0 <= x <= 2312^{31} - 1

解法：

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
26
27
class Solution {
    public int mySqrt(int x) {
        if (x < 1) return 0;
        long left = 1;
        long right = x;
        long mid = (left + right) / 2;
        long result = 1;

        while (left < right) {
            if (mid == left) {
                result = mid;
                break;
            }
            if (mid * mid > x) {
                right = mid;
            } else if (mid * mid < x) {
                left = mid;
            } else {
                result = mid;
                break;
            }
            mid = (left + right) / 2;
        }

        return (int)result;
    }
}

原题链接：https://leetcode.cn/problems/sqrtx/