題目描述
給定一個非負數的x
整數,計算並回傳x
開根號的結果。
由於回傳的型別是一個整數,小數位數會被裁切掉,結果只有整數的部份會被回傳。
備註:您不被允許使用任何內建的指數函數或是運算子,例如pow(x, 0.5)
,或是x ** 0.5
、x ^ 0.5
。
原題網址
輸入格式
範例輸入1
x = 4
範例輸出1
2
範例輸入2
x = 8
範例輸出2
2
題解
這題可以利用二元搜尋法的概念來解:
值得注意的是,在比較數值是否為傳入數值的平方根時,應使用除法,而不是乘法,避免溢位。
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;
};