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