```
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0:
return 0
low=1
high=x
while True:
mid=(low+high)//2
if mid==x/mid:
return mid
elif mid<x/mid:
low=mid+1
if mid+1>x/(mid+1):
return mid
else:
high=mid
```