LeetCode 69. Sqrt(x) 解题思路和python代码

题目：
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.

Constraints:

0 <= x <= 231 - 1

思路：
输入的是一个非负数x，需要返还x的开平方，并且需要是一个向下约的整数。

我们可以使用binary search去完成这个题目。
从[0, x]这个范围开始做binary search，首先检查中间点mid。
如果mid的2次方是x，那么mid就正好是x的开平方。
如果mid的2次方要小于x，证明应该向右移动mid，去找更大的数，将low更新为mid+1。
如果mid的2次方要大于x，证明应该向左移动mid，去找更小的数，将high更新为mid-1。

这个解决方案的time complexity是O(log x)。

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