LeetCode 69. Sqrt(x)

Description

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.

Example 1:

Input: 4

Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

描述

实现int sqrt（int x）.

计算并返回x的平方根，其中x保证为非负整数.

由于返回类型是整数，因此将截断十进制数字，并仅返回结果的整数部分.

思路

• 对一个数实现开方，并返回其整数部分
• 此题目使用二分法.
• 我们初始化left,right,middle = 0,x,x>>1(位运算，等同于x/2，位运算速度更快).
• 如果middle*middle < x,说明sqrt(x)在[middle,right]之间，我们更新left==middle，middle == left + ((right - left)>>1).
• 如果middle*middle > x，说明sqrt(x)在[left,middle]之间，我们更新right == millde,middle = left + ((right - left)>>1).
• 结束条件:当middlemiddle <= x <(middle+1)(midddle+1)时，返回middle.

class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        # 如果输入是1，则直接返回1
        if x == 1:
            return 1
        # 左边界，右边界，中间值，注意位运算9>>1=4,为整型
        left, right, middle = 0, x, x >> 1
        while True:
            # 对中间的值求平方
            multi = middle*middle
            # 如果平方小于x，说明sqrt(x)在[middle,right]之间
            if multi < x:
                left = middle
            # 如果平方大于x，说明sqrt(x)在[left,middle]之间
            elif multi > x:
                right = middle
            # 求middle+1的平方
            intmultib = (middle+1)*(middle+1)
            # 如果x落在了[middle,middle+1)之间，结束循环，返回middle
            if multi <= x < intmultib:
                return middle
            middle = left+((right-left) >> 1)
if __name__ == "__main__":
    so = Solution()
    res = so.mySqrt(190983754751)
    print(res)

源代码文件在这里.