C++ 面试高频考点 力扣 69. x 的平方根 二分查找 题解 每日一题

如果是第一次刷到这篇博客的朋友，先跟你说句 “欢迎～”！ “x 的平方根” 这道题可以用二分查找来解决，而二分查找有两个核心基础需要吃透：一是 “朴素二分查找”（处理无重复元素的简单查找），二是 “二分查找的左右边界模板”（处理 “找第一个 / 最后一个满足条件的元素”）。

如果目前对 “二分查找的二段性本质”“循环条件为什么是 left<right”“middle 取整怎么避坑” 这些细节还不太清楚，建议先看看我前两个基础篇博客，我会通过两道典型的二分算法题目能帮你搭建好二分查找的核心逻辑框架：

1.C++ 面试高频考点 力扣 704.二分查找 基础二分查找
2.C++ 面试高频考点 力扣 34. 在排序数组中查找元素的第一个和最后一个位置 二分查找左右端点

而今天要讲的 “x 的平方根”，正是 “右边界查找模板” 的经典实战题 —— 学会这道题，就能彻底搞懂 “如何找满足条件的最后一个元素”，后续遇到类似变形题也能轻松应对～

题目描述

题目链接：力扣 69. x 的平方根

题目描述：

示例 1：
输入：x = 4
输出：2
解释：4 的算术平方根是 2，返回整数部分。

示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…，小数部分舍去后返回 2。

提示：
0 <= x <= 2^31 - 1

这道题为什么能用二分查找？

在写代码前，我们得先明确“这道题的二分逻辑是什么”——毕竟不是所有题都能套二分，核心还是看是否满足“二段性”。

首先，算术平方根的定义是：找到一个最大的整数 ans，使得 ans² ≤ x（因为要舍去小数部分，比如 x=8 时，2²=4≤8，3²=9>8，所以 ans=2）。

从这个定义里，我们能直接提炼出“二段性”：

• 左半部分：所有整数 k 满足 k² ≤ x（这部分包含我们要找的“最大 ans”）；
• 右半部分：所有整数 k 满足 k² > x（这部分一定不包含目标 ans）。

比如 x=8 时：

• 左半部分（k² ≤8）：1、2；
• 右半部分（k² >8）：3、4、…、8。

我们要找的“最大 ans”，就是左半部分的最后一个元素——这正好对应我们之前学的“右边界查找模板”！因为右边界查找的核心就是“找满足条件的最后一个元素”，这里的“条件”就是 k² ≤x。

细节问题分析

问题1：循环的判断条件用什么？什么时候结束？

我们要先明确：循环的目标是找到符合题目条件的数，所以我们要“让left和right最终指向同一个位置”
我们要找的 “最大 ans”是唯一的，所以最终 left 和 right 必须重合，这个重合点就是答案。而 left < right 这个条件，就是为了“在 left 和 right 不重合时持续缩小范围”，直到两者相等——循环结束的标志就是 left == right。

为什么不能用 left <= right？举个例子：
假设 x=4，此时 left=1，right=4，最终会缩到 left=2，right=2。如果用 left <= right，循环会继续执行：

• middle = 2 + (2-2+1)/2 = 2；
• 满足 middle² ≤4，left=2；
• 此时 left 仍等于 right，循环再次执行，陷入死循环。

所以用 left < right 能避免死循环，因为一旦 left == right，循环直接退出，此时的 left = right 也就是答案。

问题2：left/right 指针如何根据中间值移动？

这个问题的核心是“判断 middle 是否在目标区间内”，会有两种可能：

情况1：如果 middle² >x
右半部分的元素都不满足条件，所以 middle 一定不是答案，甚至 middle 右边的元素也都不是答案（因为 k 越大，k² 越大）。所以直接把 right=middle-1，把 middle 及其右边的元素全部舍弃，范围缩小到 [left, middle-1]。
如图中前两步：

为什么不能让 right=middle？
比如 x=8，middle=3（3²=9>8），如果 right=3，范围变成 [1,3]，下次循环还会包含 3 这个无效元素，可能导致死循环。

情况2：当 middle² ≤ x 的时候
此时middle所在的区间是可能包含正确答案的区间也就是left,right的左半部分，那么左半部分的“最后一个元素”是我们的目标（因为单调性），而 middle 可能就是这个“最后一个元素”，也可能在它左边。
比如

到图中最后一步时候x=8，middle=2 时，2²=4≤8
此时目标 ans 就是2，所以不能舍弃 middle，必须让 left=middle（把范围缩小到 [middle, right]），继续找左半部分的最后一个元素，或者循环结束。

那么为什么不能让 left=middle+1？
如果 x=8，middle=2，此时 left=2+1=3，范围变成 [3,4]，而目标 ans=2 已经被排除了——这就会漏查！

完整代码及注释

基于上面的分析，给代码加上详细注释，方便你对照理解：

class Solution {
public:
    int mySqrt(int x) {
        // 特殊情况：x=0时，平方根是0，单独处理（避免left=1>right=0的错误）
        if (x == 0) {
            return 0;
        }

        // 初始化范围：x≥1时，平方根的范围是[1, x]（比如x=1，平方根是1；x=2，平方根≤2）
        int left = 1;
        int right = x;

        // 循环条件：left < right，直到left==right时结束（此时重合点就是答案）
        while (left < right) {
            // 1. 计算middle：用left + (right-left+1)/2实现向上取整，避免死循环
            // 2. 用long long存储middle：防止middle*middle超过int最大值（比如x=2^31-1时，middle可能是1e5，平方后超int）
            long long middle = left + (right - left + 1) / 2;

            // 判断middle是否在左半部分（满足k² ≤x）
            if (middle * middle <= x) {
                // 是：middle可能是目标（最大ans），不能舍弃，left移到middle（范围缩小到[middle, right]）
                left = middle;
            } else {
                // 否：middle在右半部分（k² >x），直接舍弃middle及右边，right移到middle-1（范围缩小到[left, middle-1]）
                right = middle - 1;
            }
        }

        // 循环结束时left==right，这个重合点就是最大的ans
        return left;
    }
};

细节问题分析：

为什么 middle 计算要加1？（避免死循环的关键）
代码里用了 middle = left + (right - left + 1)/2，这里的“+1”是为了让 middle“向上取整”，而不是默认的“向下取整”。如果不加1，会出现死循环！

举个反例：x=2，left=1，right=2：

• 不加1时，middle = 1 + (2-1)/2 = 1（向下取整）；
• 满足 1² ≤2，left=1（还是1）；
• 此时 left=1，right=2，下次循环 middle 还是1，陷入死循环。

加1之后：

• middle = 1 + (2-1+1)/2 = 2（向上取整）；
• 2²=4>2，right=2-1=1；
• 此时 left=1，right=1，循环结束，返回1（正确）。

本质原因：当 left 和 right 相差1时（比如 left=k，right=k+1），如果用向下取整，middle 会等于 left，此时如果满足条件 middle² ≤x，left 不会变化，导致范围永远是 [k, k+1]，陷入死循环。而向上取整能让 middle 等于 right，通过判断直接调整 right，避免死循环。

为什么要处理x=0的情况？为什么left从1开始？
代码里先判断了 x=0 并返回0，这是必要的，因为：

• 0的平方根是0，如果不单独处理，left=1，right=0，此时 left > right，循环不执行，直接返回 left=1（错误）；
• 当 x≥1 时，平方根的范围是 [1, x]（比如 x=1，平方根是1；x=10，平方根最大是3，小于10），所以 left 从1开始，right 从x开始，能减少不必要的范围。

避坑指南：这3个错误90%的人都会犯

结合这道题，总结二分查找的高频坑点，帮你避开：

这道题如何对应“右边界查找模板”？

最后再把这道题和右边界查找模板对应起来，帮你建立“题→模板”的映射思维，以后遇到类似题就能直接套用：

总结

这道题看似简单，但里面的“向上取整”“循环结束条件”“范围调整规则”都是二分查找的核心细节。其实所有二分查找题的本质都是“找对二段性，选对模板”：

1. 先明确“要找的元素是什么”（本题是“最大的k满足k² ≤x”）；
2. 再划分“二段性”（满足条件的左半部分，不满足的右半部分）；
3. 最后根据“找左边界还是右边界”选模板（本题是右边界，所以用向上取整+left=middle）。

下次再遇到二分题，先问自己这三个问题，就能避开80%的坑！

“Doro又带着小花🌸来啦！这道x的平方根是不是把‘右边界模板’的细节讲透了呀？只要把‘循环结束条件’和‘middle取整’这两个点吃透，以后遇到‘找满足条件的最后一个元素’的题，就能直接套用啦～如果觉得这篇拆解帮你理清了思路，别忘了点赞收藏，下次遇到二分题想不起来细节时，就能快速翻到啦～”
关注博主，后面还会一起攻克更多二分变形题，从‘会写’到‘写对’，慢慢进阶！