一.问题描述
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4 Output: 2
Example 2:
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
二.解题思路
方法一：迭代
从0~i开始迭代，知道i*i大于x的时候，返回i-1.
时间复杂度:O(N)。
方法二:二分法
这道题其实就是然我们从0~x中，找一个数满足 i*i<=x and (i+1)*(i+1)>x。
和二分法的思路差不多，注意结束条件，结束条件l>r，返回值l-1，原因参考结束条件（当l超过r的时候，说明l-1太小，但是l=r，说明l又太大)。
具体可以参考第三部分的源码。
时间复杂度O(logN)。
方法三：built-in函数：
这个就没啥好说的了。看代码吧，最快的。
更多leetcode算法题解法: 专栏 leetcode算法从零到结束 或者 leetcode 解题目录 Python3 一步一步持续更新～
三.源码
方法一：
class Solution:
def mySqrt(self, x: int) -> int:
i=0
while i*i<=x:
i+=1
return i-1
方法二：
class Solution:
def mySqrt(self, x: int) -> int:
l,r=0,x
while l<=r:
mid=(l+r)//2
temp=mid**2
if temp==x:return mid
elif temp>x:r=mid-1
else:l=mid+1
return l-1
方法三：
class Solution:
def mySqrt(self, x: int) -> int:
return math.floor(math.sqrt(x))