69 x 的平方根

标签: 二分搜索

题目

题目链接：69 x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

思路

二分法：本题采用 二分搜索总结 里的「模版 I」实现

1. 初始化：
   1. 左指针：1，因为平方根至少大于等于 1.
   2. 右指针：x // 2，因为当 $x >= 4$ 时，$x <= (\frac{x}{2})^{2}$，有 $\sqrt{x} <= \frac{x}{2}$，即 $x$ 的平方根最大值也就达到 $\frac{x}{2}$.
2. 终止条件：$left > right$
3. 指针移动：当 mid * mid != x 时，无论是向左还是向右移动，都不会是原来的 mid。（模版 II 和模版 III 都有指针不移动的情况）

代码

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return x
        if x < 4: return 1
        
        # 初始化
        left, right = 1, x // 2

        # 终止条件
        while left <= right:
            mid = (left + right) // 2

            if mid * mid == x:
                return mid
            # mid * mid != x 就要移动指针
            elif mid * mid < x:
                left = mid + 1
            else:
                right = mid - 1

        return right

分析

时间复杂度需要 O(log n)；空间复杂度需要 O(1)，常数个变量即可。