The main thought of my algorithm is binary search. Cost 77ms.

```
class Solution:
# @param x, an integer
# @return an integer
def sqrt(self, x):
if x == 0:
return 0
low = 1
high = x
mark = 1
while low != high - 1:
mid = (high + low) / 2
if mid * mid > x:
high = mid
elif mid * mid < x:
mark = mid
low = mid
else:
return mid
return mark
```

And I changed **yuyibestman** and **tyuan73**'s java codes which using math method into python and improved a little bit. Cost 79ms.

```
class Solution:
# @param x, an integer
# @return an integer
def sqrt(self, x):
ans = 0
bit = 1l << 15
while bit > 0:
ans |= bit
if ans * ans > x:
ans ^= bit
bit >>= 1
return int(ans)
```

Wish these codes can help you.