当前位置：首页 > article >正文

3.4 二分查找专题：LeetCode 69. x 的平方根

article 2025/3/19 16:57:39

1. 题目链接

LeetCode 69. x 的平方根

2. 题目描述

给定一个非负整数 x，计算并返回 x 的平方根的整数部分（向下取整）。
示例：

输入：x = 4 → 输出：2
输入：x = 8 → 输出：2（实际平方根为 2.828，取整数部分）。

3. 示例分析

目标值是完全平方数：
- x = 16 → 返回 4。
目标值非完全平方数：
- x = 10 → 返回 3（3^2 = 9 ≤ 10，4^2 = 16 > 10）。

4. 算法思路

二分查找法：

初始化指针：left = 1，right = x（处理 x = 0 的特殊情况直接返回 0）。
循环缩小范围：
- 计算中间值 mid = left + (right - left + 1) / 2（向上取整，避免死循环）。
- 若 mid * mid ≤ x，说明目标在右半区间，调整 left = mid。
- 若 mid * mid > x，说明目标在左半区间，调整 right = mid - 1。
终止条件：当 left == right 时，返回 left（最大满足 k^2 ≤ x 的整数）。

5. 边界条件与注意事项

处理 x < 1：直接返回 0，避免进入循环。
溢出问题：中间值 mid 使用 long long 类型，防止 mid * mid 溢出。
循环终止条件：必须使用 mid 的向上取整，否则可能陷入死循环（例如 x = 2）。

6. 代码实现

class Solution 
{
public:
    int mySqrt(int x) 
    {
        if(x < 1) return 0;
        int left = 1, right = x;
        while(left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

在这里插入图片描述

暴力枚举法与二分查找法对比图表

对比维度	暴力枚举法	二分查找法
核心思想	遍历 `0` 到 `√x`，找到最大的 `k` 满足 `k² ≤ x`。	二分法缩小范围，定位最大满足 `k² ≤ x` 的整数。
时间复杂度	O(√x)（需要遍历最多 `√x` 次）。	O(log x)（每次将搜索范围缩小一半）。
空间复杂度	O(1)（无需额外存储）。	O(1)（仅需常数变量记录指针）。
实现方式	单层循环逐个判断。	循环调整左右指针，计算中间值并比较。
适用场景	极小数据规模（`x ≤ 1e3`）。	任意规模数据（尤其适合 `x ≥ 1e6`）。
优点	实现简单，无需处理复杂边界条件。	时间复杂度极低，适合处理大规模数据。
缺点	数据规模大时性能极差（例如 `x=1e18` 时需 `1e9` 次操作）。	需处理整数溢出和中间值取整逻辑。