给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例

输入：x = 8  输出：2

输入：x = 4  输出：2

解析

1）不允许使用内置指数函数，而且会舍弃小数部分，不是精准值，说明只能挨个尝试了

2）挨个尝试，数字大小相关的问题，都可以考虑二分查找，速度更快

代码示例 

def mySqrt(self, x: int) -> int:
    left = 0
    right = x
    while left <= right:
        mid = (left + right) // 2
        s = mid * mid
        if s < x:
            left = mid + 1
        elif s > x:
            right = mid - 1
        else:
            return mid
    return left - 1

print(mySqrt(8))

执行用时：36 ms, 在所有 Python3 提交中击败了 92.45% 的用户.

本文为 陈华 原创，欢迎转载，但请注明出处：http://www.ichenhua.cn/read/364