x 的平方根

Category	Difficulty	Likes	Dislikes
algorithms	Easy (38.43%)	1375	-

Tags

math | binary-search

Companies

apple | bloomberg | facebook

给你一个非负整数 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 <= 2<sup>31</sup> - 1

Discussion | Solution

解法

 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
28
29
30
31
struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 二分法
    pub fn my_sqrt(x: i32) -> i32 {
        use std::cmp::Ordering;

        if x < 2 {
            return x;
        }
        let mut res = 0;
        let (mut l, mut r) = (0, x / 2 + 1);
        while l <= r {
            let m = l + (r - l) / 2;
            match m.cmp(&(x / m)) {
                Ordering::Equal => return m,
                Ordering::Greater => r = m - 1,
                Ordering::Less => {
                    l = m + 1;
                    res = m
                }
            }
        }

        res
    }
}
// @lc code=end

x 的平方根

x 的平方根

解法

相关文章：