需求
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
分析
可以使用二分查找的思路来求解算术平方根。
首先,设定搜索范围,最小值为0,最大值为x。
然后,通过二分查找的方式逼近算术平方根。
每次选取中间值mid,计算mid的平方。如果平方小于等于x,说明mid可能是答案的一部分,更新最小值为mid,继续搜索mid右边的范围。
如果mid的平方大于x,说明mid不是答案的一部分,更新最大值为mid。
当搜索范围缩小到最小值和最大值相等时,返回最小值即可。
代码
class Solution:
def x_sqrt(self,x):
left=0
right=x
while left<=right:
mid=(left+right)//2
if mid*mid <= x <(mid+1)*(mid+1):
return mid
elif mid*mid<x:
left=mid+1
else:
right=mid-1
if __name__ == '__main__':
call=Solution()
x=8
print(call.x_sqrt(x))