Python二分法求平方根

二分法是一种常用的查找算法，可以用来在有序数组中查找特定元素。在这个问题中，我们可以使用二分法来求解平方根。具体步骤如下：

1. 定义left为0，right为传入的那个数字x。
2. 假定此时的mid：mid = (left + right) // 2。
3. 进行判断，若 mid * mid = x，则返回mid。
4. 若出现mid * mid > x的情况，则说明需要求的算术平方根在mid的左边，将right更新为mid-1。
5. 若出现mid * mid < x的情况，则说明需要求的算术平方根在mid的右边，将left更新为mid+1。
6. 重复步骤2-5，直到left>right，此时返回ans即可。

下面是Python代码实现：

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