mySqrt 解题思路（二分查找）
题目
求非负整数x的整数平方根（向下取整），即最大的整数r满足r * r <= x。不能使用内置sqrt。
例如：
x = 4→2x = 8→2（因为2*2=4 <= 8，3*3=9 > 8）x = 0→0
核心思想：在[0, x]里二分找「最大的可行值」
平方根r一定在[0, x]范围内（x >= 1时r <= x）。这个区间是单调的：
若
mid * mid <= x，说明mid可行，答案至少是mid，往右找更大的若
mid * mid > x，说明mid太大，答案在左边
于是可以用二分查找，不断缩小区间，直到锁定答案。
关键：判断条件从「比较大小」变成「比较平方」
普通二分是找nums[mid] == target，这题的「条件」是：
text
mid * mid <= x → mid 是可行解，答案在 mid 或其右边 mid * mid > x → mid 太大，答案在 mid 左边
所以：
python
if mid * mid <= x: left = mid + 1 # mid 可行，尝试更大的 else: right = mid - 1 # mid 太大，往左缩
为什么循环结束后返回right
用while left <= right，循环结束时一定是left = right + 1（left刚越过right）。此时：
right是最后一个满足mid*mid <= x的位置→ 就是向下取整的平方根✅left是第一个mid*mid > x的位置→ 是平方根 + 1
所以返回right。
一句话：
right停在「可行区的右边界」，left停在「不可行区的左边界」，答案在right。
代码
class Solution: def mySqrt(self, x: int) -> int: left, right = 0, x while left <= right: mid = (left + right) // 2 if mid * mid <= x: left = mid + 1 # mid 可行，往右找更大 else: right = mid - 1 # mid 太大，往左缩 return right # 最大的可行值 = 平方根执行流程演示
例 1：x = 8（答案 2）
text
left=0, right=8 mid=4: 16>8 → right=3 mid=1: 1<=8 → left=2 mid=2: 4<=8 → left=3 mid=3: 9>8 → right=2 left=3 > right=2 → 结束，return right=2 ✅
例 2：x = 4（答案 2）
text
left=0, right=4 mid=2: 4<=4 → left=3 mid=3: 9>4 → right=2 left=3 > right=2 → 结束，return right=2 ✅
例 3：x = 0（答案 0）
text
left=0, right=0 mid=0: 0<=0 → left=1 left=1 > right=0 → 结束，return right=0 ✅
例 4：x = 1（答案 1）
text
left=0, right=1 mid=0: 0<=1 → left=1 mid=1: 1<=1 → left=2 left=2 > right=1 → 结束，return right=1 ✅
边界与正确性
| 情况 | 处理 |
|---|---|
x = 0 | right=0，返回 0 ✅ |
x = 1 | 返回 1 ✅ |
x是完全平方数（4、9、16） | 返回精确平方根 ✅ |
x不是完全平方数（8） | 返回向下取整 ✅ |
x很大 | mid*mid在 Python 不会溢出（大整数），其他语言需防溢出 |
为什么right = x而不是x - 1：x=0时x-1=-1会越界/跳过循环；x=1时x-1=0也边界紧张。用x覆盖[0, x]最安全。
复杂度
时间：
O(log x)，每次区间减半空间：
O(1)，只用几个变量
易错点
| 易错点 | 错误写法 | 正确 |
|---|---|---|
mid公式 | left + right // 2 | (left + right) // 2 |
mid位置 | 在循环外算一次 | 循环内每轮重算 |
| 循环条件 | while left < right | while left <= right |
return位置 | 写在循环里 | 循环外 |
| 返回值 | return left | return right |
| 右边界 | right = x - 1 | right = x |
| 比较 | mid > x | mid * mid > x |
一句话记忆
在
[0, x]里二分，mid*mid <= x就往右找（left=mid+1），否则往左缩（right=mid-1）；循环结束left=right+1，返回right即向下取整平方根。判断条件是「平方比较」，不是「大小比较」。
