[LeetCode]開根號 Sqrt(x)

題目描述

給定一個非負數的x整數，計算並回傳x開根號的結果。

由於回傳的型別是一個整數，小數位數會被裁切掉，結果只有整數的部份會被回傳。

備註：您不被允許使用任何內建的指數函數或是運算子，例如pow(x, 0.5)，或是x ** 0.5、x ^ 0.5。

原題網址

https://leetcode.com/problems/sqrtx/

輸入格式

0 <= x <= 2³¹ - 1

範例輸入1

x = 4

範例輸出1

範例輸入2

x = 8

範例輸出2

題解

這題可以利用二元搜尋法的概念來解：

https://magiclen.org/binary-search/

值得注意的是，在比較數值是否為傳入數值的平方根時，應使用除法，而不是乘法，避免溢位。

參考答案

use std::cmp::Ordering;

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }

        let mut s = 1;
        let mut e = x;

        while s <= e {
            let m = s + ((e - s) >> 1);

            // (m*m).cmp(&x)
            match m.cmp(&(x / m)) {
                Ordering::Equal => {
                    return m;
                }
                Ordering::Greater => {
                    e = m - 1;
                }
                Ordering::Less => {
                    s = m + 1;
                }
            }
        }

        e
    }
}

const mySqrt = (x: number): number => {
    if (x === 0) {
        return 0;
    }

    let s = 1;
    let e = x;

    while (s <= e) {
        const m = s + ((e - s) >>> 1);

        const xdm = Math.floor(x / m);

        if (m === xdm) {
            return m;
        } else if (m > xdm) {
            e = m - 1;
        } else {
            s = m + 1;
        }
    }

    return e;
};