题目: X 的平方根

方法一：二分查找

思路：由于 x 的平方根一定小于 x，大于等于 0，所以可以在 0 到 x 之间进行二分查找，找到最大的 mid 值，使得 mid 的平方小于等于 x。

代码（Python）：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        left, right = 0, x
        while left < right:
            mid = (left + right + 1) // 2
            if mid * mid <= x:
                left = mid
            else:
                right = mid - 1
        return left

方法二：牛顿迭代法

思路：可以使用牛顿迭代法求解平方根，不断迭代，直到达到精度要求。公式为：f(x) = x^2 - n，f'(x) = 2x，根据牛顿迭代公式，可以得到：x = (x + n / x) / 2。不断迭代，直到达到精度要求。

代码（Python）：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        cur, pre = 1, 0
        while abs(cur - pre) > 1e-6:
            pre = cur
            cur = (cur + x / cur) / 2
        return int(cur)

方法三：数学公式

思路：根据泰勒展开式，可以得到：sqrt(x) = x / (2 * sqrt(x)) + 1 / 2 * (sqrt(x) - x / (2 * sqrt(x))) - 1 / 8 * (sqrt(x) - x / (2 * sqrt(x)))^2 + ...。不断迭代，直到达到精度要求。

代码（Python）：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans + 1 if (ans + 1) ** 2 <= x else ans