LeetCode_Sqrt X

Posted on | In | Views:

Sqrt(x)

Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
（实现Sqrt(x)）

Example:



1. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def mySqrt(self, x: 'int') -> 'int':
        left, right = 0, x
        
        while left <= right:
            middle  = (left + right)//2
            if middle * middle <= x and (middle+1) * (middle+1) > x:
                return middle
            elif middle * middle < x:
                left = middle + 1
            else:
                right = middle - 1