[LeetCode] 69. Sqrt(x)

轉自LeetCode

Implement int sqrt(int x).

Compute and return the square root of x.

<Solution>

這題有兩種解法，一種是二分法，一種是牛頓法 (資料1, 資料2)

這邊使用牛頓法來處理

x_i+1=x_i - (x_i² - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2

code 如下
c++

還有另一種不需要被數學公式的解法

在 1 到 x 之間，使用 binary search 來找

kotlin，time complexity = O(logN)