x 的平方根 Sqrt(x)

问题描述

这个比较适合二分查找法, 比较容易理解.

#![allow(unused)]
fn main() {
// Binary Search
pub fn my_sqrt1(x: i32) -> i32 {
    assert!(x >= 0);

    if x == 0 || x == 1 {
        return x;
    }

    let mut left: i32 = 0;
    let mut right: i32 = x;
    let mut ans: i32 = 0;

    while left <= right {
        let middle: i32 = left + (right - left) / 2;
        let square = middle.saturating_mul(middle);
        if square > x {
            // 值太大了, 右侧的值向左移
            right = middle - 1;
        } else {
            ans = middle;
            // 有些小, 左侧的值向右移
            left = middle + 1;
        }
    }
    ans
}
}

下面方法是二分查找法的另一个写法, 其边界值的判定条件跟上述方法有所差别:

#![allow(unused)]
fn main() {
// Binary Search
pub fn my_sqrt2(x: i32) -> i32 {
    let mut left = 0;
    let mut right = x;

    while left < right {
        let middle = left + (right - left + 1) / 2;
        let square = middle.saturating_mul(middle);
        if square > x {
            right = middle - 1;
        } else {
            // 注意这里的边界情况.
            left = middle;
        }
    }
    left
}
}