題目描述

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



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

備註:您不被允許使用任何內建的指數函數或是運算子,例如pow(x, 0.5),或是x ** 0.5x ^ 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/

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

參考答案