题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例1：

输入：x = 4
输出：2

示例2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

想法：

• 使用2分查找法进行查找

遇到困难：

• 怎么定位到第一个平方大于target的位置

解决困难：

• 改为return部分为left的版本

代码如下：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        elif x<4:
            return 1

        left = 2
        right = x // 2
        
        while left < right:
            mid = (left+right) //2
            if mid * mid < x:
                left = mid+1
            elif mid * mid >= x:
                right = mid
        
        if left*left <= x:
            return left
        else:
            return left-1 

提交结果：

执行用时：24 ms, 在所有 Python 提交中击败了78.16%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了62.93%的用户
通过测试用例：
1017 / 1017

尝试新方法

class Solution(object):
    def mySqrt(self, x):
        left = 0
        right = x
        if x == 1 or x == 0:
            return x
        while left < right:
            mid = (right + left) // 2
            if mid **2 > x:
                right = mid - 1
            else:
                left = mid + 1
                
        if left **2 > x:  # 先判断麻烦的
            return left - 1 
        else:
            return left