leetcode | sqrt

69.sqrt(x)

题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题目链接

思路

1.二分法

代码

class Solution(object):
    @staticmethod
    def my_sqrt1(a):
        """二分法开根号"""
        # 初始化左右边界
        left, right = 0, a
        while left <= right:
            mid = (left + right) // 2
            if mid ** 2 == a:
                return mid
            elif mid ** 2 > a:
                right = mid - 1
            else:
                left = mid + 1
        return right


if __name__ == "__main__":
    a = 3
    s = Solution()
    sqrt_a = s.my_sqrt1(a)
    print(sqrt_a)