LeetCode 69. x 的平方根：两种解法详解
LeetCode 上的经典基础题——69. x 的平方根。这道题看似简单，却能很好地考察我们对基础算法的理解，尤其是循环和二分查找的应用。题目要求很明确：给定一个非负整数 x，计算它的算术平方根，返回整数部分（舍去小数），并且不能使用任何内置指数函数和算符（比如 pow(x, 0.5) 或 x ** 0.5）。
一、题目核心解读
先再明确一下题目边界和要求，避免踩坑：
输入 x 是非负整数（0、1、2、3…），所以不需要处理负数场景；
返回值是算术平方根的整数部分，比如 x=8，平方根是2.828…，返回2；x=4，返回2；x=0，返回0；
核心限制：不能用内置指数相关方法，只能靠基础的循环、判断实现。
这道题的核心本质：找到最大的整数 res，使得 res² ≤ x 且 (res+1)² > x。所有解法都是围绕这个核心展开的，只是效率不同。
二、解法一：暴力循环（简单易理解，适合入门）
1. 思路分析
暴力循环的思路非常直观：从1开始逐个遍历，找到满足 res² ≤ x 的最大整数。但这里有个小优化——我们不需要遍历到 x，因为一个数的算术平方根最大不会超过它的一半（除了0和1）。比如 x=100，平方根是10，刚好是100的一半；x=101，平方根约10.05，也不超过50（101/2≈50.5）。所以遍历范围可以缩小到 1 到 x/2，减少循环次数。
特殊处理：当 x=0 时，直接返回0（因为0的平方根是0）；当 x=1 时，x/2=0.5，循环不会执行，此时res初始化为1，刚好返回正确结果。
2. 完整TS代码
functionmySqrt_1(x:number):number{if(x===0)return0;letres=1;for(leti=1;i<=x/2;i++){if(i*i<=x){res=i;}}returnres;};3. 优缺点分析
优点：逻辑简单，代码量少，容易上手，适合刚接触算法的同学理解题目核心；
缺点：效率较低，时间复杂度是 O(√x)（虽然遍历到x/2，但本质还是和平方根成正比）。当x很大时（比如x=2³¹-1，即最大的32位非负整数），循环次数会非常多，可能导致超时。
三、解法二：二分查找（高效最优，面试首选）
既然暴力循环效率不高，我们可以用二分查找来优化。二分查找的核心是“缩小查找范围”，每次排除一半的无效数据，时间复杂度可以降到 O(log x)，是这道题的最优解法，也是面试中常考的思路。
1. 思路分析
首先确定查找范围：左边界 left=0，右边界 right 我们可以优化为 Math.max(x >> 1, 1)。这里的 x >> 1 是位运算，等价于 Math.floor(x/2)，比直接除以2更高效；而 Math.max(…, 1) 是为了处理 x=1 的情况（此时x>>1=0，right设为1，避免查找范围出错）。
然后进行二分循环：
计算中间值 mid = (left + right) >> 1（同样用位运算优化，等价于 Math.floor((left+right)/2)）；
判断 mid² 与 x 的关系：
如果 mid² ≤ x：说明 mid 可能是我们要找的结果，但还可能有更大的数满足条件，所以更新 res=mid，同时将左边界 left 右移（left=mid+1），继续查找右半部分；
如果 mid² > x：说明 mid 太大了，需要缩小范围，将右边界 right 左移（right=mid-1）；
循环结束条件：left > right，此时 res 就是满足条件的最大整数（即算术平方根的整数部分）。
2. 完整TS代码
functionmySqrt(x:number):number{letleft=0;letright=Math.max(x>>1,1);letres=0;while(left<=right){constmid=(left+right)>>1;if(mid*mid<=x){left=mid+1;res=mid;}else{right=mid-1;}}returnres;};3. 关键细节&优缺点
关键细节：为什么用 mid * mid 不会溢出？在TS中，number类型是64位浮点数，对于x≤2³¹-1（LeetCode题目中的输入范围），mid最大是 (2³¹-1)/2 ≈1e9，mid²≈1e18，而64位浮点数可以表示的整数范围远大于这个值，所以不会溢出。如果是其他语言（比如Java），可能需要用 long 类型避免溢出，这里TS不需要担心。
优点：效率极高，时间复杂度 O(log x)，即使x是最大的非负整数，循环次数也只有30次左右，不会超时；
缺点：逻辑比暴力循环稍复杂，需要理解二分查找的“缩小范围”思路，新手可能需要多调试几次。
四、两种解法对比&实战建议
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力循环 | O(√x) | O(1) | 入门理解题目、x较小的场景 |
| 二分查找 | O(log x) | O(1) | 面试、x较大的场景（推荐） |
五、总结与解题感悟
综上所述，LeetCode 69. x 的平方根作为一道基础且经典的算法题型，在算法学习与面试考核中均占据重要地位。从算法学习维度来看，该题目无需依赖复杂数据结构与高级算法思想，是检验开发者对循环逻辑、二分查找两大基础算法掌握程度的核心载体，既能帮助新手快速建立算法解题思维，也能让有一定基础的开发者巩固核心知识点、梳理算法优化逻辑。从面试场景来看，该题目是大厂面试中考察基础算法思维的高频题型，面试官不仅关注解题代码的正确性，更注重开发者对不同解法的选择逻辑、时间复杂度与空间复杂度的分析能力，以及对边界场景的处理细节，而本题的两种核心解法（暴力循环与二分查找），恰好能全面展现开发者的基础算法素养与问题优化能力。此外，该题目还具备极强的延伸性，其核心解题思想可迁移至平方根相关的拓展题型，进一步体现了其作为基础题目的实用价值与学习意义。