YSMull
<-- algorithm



原题链接

2021/04/13

整数闭区间的二分搜索

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        return Solution::my_sqrt_i64(x as i64);
    }
    pub fn my_sqrt_i64(x: i64) -> i32 {
        let mut i = 0;
        let mut j = x;
        while i < j {
            let m = i + (j - i + 1) / 2;
            if m * m == x {
                return m as i32;
            }
            if m * m < x {
                i = m;
            } else {
                j = m - 1;
            }
        }
        return i as i32;
    }
}

直接使用二分法求近似解

这里有两个 trick：

  1. 误差 e 要取得足够小，一般推荐 e 取 $10^{-8}\sim10^{-6}$ 。
  2. 返回的根要加上 e 进行修正，使它落在根的右边（结合1，不至于导致越过下一个整数）。
impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        return Solution::my_sqrt_i64_float(x as i64);
    }
    pub fn my_sqrt_i64_float(x: i64) -> i32 {
        let e = 0.000001;
        let mut i = 0.0;
        let mut j = x as f64;
        while (j - i).abs() > e {
            let m = i + (j - i) / 2.0;
            if m * m < x as f64 {
                i = m;
            } else {
                j = m;
            }
        }
        return (i + e) as i32;
    }
}