69. Sqrt(x)

69. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

还是二分的变化 , 可以使用区间的模板 ， 对end判断

如果 int 转为 double 的话 ， 如果 x <=1 ，那么 end 就是 1.0 1e-12 可以表示两个浮点数无限接近 , 而不是 start + 1 < end

---

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut ans = x as i128;
        while ans * ans > x as i128 {
            ans = (ans + x as i128 / ans) / 2;
        }
        ans as i32
    }
}

#算法/二分