x 的平方根

69. x 的平方根 - 力扣（LeetCode）

问题简述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 (整数部分)。

思路: 二分查找

Python

class Solution:
    def mySqrt(self, x: int) -> int:
        if x in (0, 1): return x

        l, r = 0, x
        while l < r:
            m = (l + r) // 2
            if m ** 2 <= x < (m + 1) ** 2:
                break
            
            if m ** 2 < x:
                l = m
            else:
                r = m
        
        return m

进阶: 浮点数版本

• 定义 mySqrt(x: float, e: int), 其中 e 为小数精度;

• 注: 代码未经过严格测试, 可能存在问题;

Python

class Solution:
    def mySqrt(self, x: float, e: int) -> int:
        if x in (0, 1): return x
        
        assert x > 0
        flag = False
        if x < 1:  # 小于 1 的情况
            x = 1 / x
            flag = True
        
        l, r = 0, x
        while l < r:
            m = (l + r) / 2
            if abs(m ** 2 - x) <= 0.1 ** e:
                break
            
            if m ** 2 < x:
                l = m
            else:
                r = m
        
        return 1 / m if flag else m