69. x 的平方根
来源: 69. x 的平方根
1. 题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
2. 解题思路
二分法查找
3. 代码
class Solution:
def mySqrt(self, x: int) -> int:
left = 0
right = (x+1) // 2
while left <= right:
mid = ( left + right ) // 2
mid_sq = mid ** 2
if mid_sq > x:
right = mid - 1
elif mid_sq < x:
left = mid + 1
else:
return mid
return right
网友评论