1、求平方根,x的整数部分
leetcode69. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,由于返回类型是整数,小数部分将被舍去。
思路关键点:
1)二分法判断条件:l<=r:
2) 循环内部判断时,<=时将中间值赋给最终要返回的值
官方解答:
二分查找解析代码如下:
class Solution:
def mySqrt(self, x: int) -> int:
l=0
r=x
ans=-1
while l<=r:
m=(l+r)//2
if m*m<=x:
l=m+1
ans=m
else:
r=m-1
return ans
2、求一定精度的平方根
思路关键点:
1)循环判断条件:l<=r
2)循环内部判断条件,如果mid*mid<n,则l=mid;否则r=mid
代码如下:
import math
def sqrtmy(n,a): #二分查找法 a是精确度
if n<=0:
return n
l=0*0.0
r=n*1.0
while l<=r:
mid=(l+r)/2.0
if abs(mid*mid-n)<=a:
return mid
elif mid*mid<n:
l=mid
else:
r=mid
return -1
print(sqrtmy(8,1e-4))
网友评论