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