binary search method
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x<=1: return x
left,right=1,x/2
while True:
mid=(left+right)/2
if mid*mid>x:
right=mid-1
else:
if (mid+1)*(mid+1)>x:return mid
left=mid+1
newton integer method
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
a=x
while a*a>x:
a=(a+x/a)/2
return a
