69X的平方根

题目：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

法一：自己的代码

思路：这道题虽然简单，但方法很灵活，这类问题主要是两点的配合，一是循环结束条件，是左闭右开还是左闭右闭，二是mid取左中位数还是右中位数，这两者直接影响了后续的判断条件，返回值时可以试几个数的left，right，方便判断

from typing import List
class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        # 加1是为了照顾到1
        right = int(x/2) + 1
        while left <= right:
            mid = (left + right) >> 1
            # 注意当left=right时，这时有两种情况，一种是等于目标值，一种是比目标值大一
            # 这两种情况最后都要返回right，举9 10两个例子可以看出来
            if mid * mid <= x:
                left = mid + 1
            else:
                right = mid - 1
            print(left, right)
        print('-' * 20, left, right)
        return right
if __name__ == '__main__':
    solution = Solution()
    result = solution.mySqrt(49)
    print(result)

View Code

法二：牛顿迭代法用于解方程