题干
69. x 的平方根
难度简单381收藏分享切换为英文关注反馈
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
思路一(二分查找)
取left, right = 0, x
由于0 <= sqrt(x) <= x
我们知道所求值就在区间[0,x],我们猜测其为mid = (left + right) // 2，当然并不一定就是
若 mid * mid < x 说明所求值在区间[mid, right] ，这时令left=mid继续迭代
若 mid * mid > x 说明所求值在区间[left, mid] ，这时令right=mid继续迭代
若mid * mid == x 则返回mid
二分的思想就是如上缩小区间直到找到最后的sqrt(x)
以上内容是二分的基本思想，对于这道题还有一些需要考虑的细节。
- 由于所求值为整数，所以不需要计算小数部分，但是当left == right - 1时，计算得到mid = left，这时再继续下去已经没有必要了，我们将区间缩小到了
[left, left + 1]若取整，直接取left即可 - 由于1中的处理方式忽略了sqrt(x) == left + 1 = right 这种情形，这种情况只会出现在sqrt(x) == x的情况下（可以思考一下为什么会这样），所以可以在开始时进行特判，或者初始化时直接将right赋值为x + 1也可以解决。
- python代码
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x + 1
while left < right - 1:
mid = (left + right) // 2
value = mid * mid
if value == x:
return mid
if value > x:
right = mid
else:
left = mid
return left return left
思路二（牛顿迭代）
- python代码
class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
r = x
temp = x / r
while r > temp:
r = (r +temp) // 2
temp = x / r
return int(r)
思路三（公式变换）
这种算法算是钻了一个孔空子，基本思想很简单
- python代码
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
ans = int(math.exp(0.5 * math.log(x)))
return ans + 1 if (ans + 1) ** 2 <= x else ans
