https://leetcode.com/problems/sqrtx/
Sqrt(x)
Total Accepted: 68881 Total Submissions: 291203 Difficulty: Medium
Implement int sqrt(int x).
Compute and return the square root of x.
Code
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
return -1
left, right = 0, x
while left <= right:
mid = left + (right - left)/2
if mid**2 < x:
left = mid + 1
elif mid**2 > x:
right = mid - 1
else:
return mid
return left-1
Idea
Binary Search