mySqrt 解题思路二分查找题目求非负整数x的整数平方根向下取整即最大的整数r满足r * r x。不能使用内置sqrt。例如x 4→2x 8→2因为2*24 83*39 8x 0→0核心思想在[0, x]里二分找「最大的可行值」平方根r一定在[0, x]范围内x 1时r x。这个区间是单调的若mid * mid x说明mid可行答案至少是mid往右找更大的若mid * mid x说明mid太大答案在左边于是可以用二分查找不断缩小区间直到锁定答案。关键判断条件从「比较大小」变成「比较平方」普通二分是找nums[mid] target这题的「条件」是textmid * mid x → mid 是可行解答案在 mid 或其右边 mid * mid x → mid 太大答案在 mid 左边所以pythonif mid * mid x: left mid 1 # mid 可行尝试更大的 else: right mid - 1 # mid 太大往左缩为什么循环结束后返回right用while left right循环结束时一定是left right 1left刚越过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 # 最大的可行值 平方根执行流程演示例 1x 8答案 2textleft0, right8 mid4: 168 → right3 mid1: 18 → left2 mid2: 48 → left3 mid3: 98 → right2 left3 right2 → 结束return right2 ✅例 2x 4答案 2textleft0, right4 mid2: 44 → left3 mid3: 94 → right2 left3 right2 → 结束return right2 ✅例 3x 0答案 0textleft0, right0 mid0: 00 → left1 left1 right0 → 结束return right0 ✅例 4x 1答案 1textleft0, right1 mid0: 01 → left1 mid1: 11 → left2 left2 right1 → 结束return right1 ✅边界与正确性情况处理x 0right0返回 0 ✅x 1返回 1 ✅x是完全平方数4、9、16返回精确平方根 ✅x不是完全平方数8返回向下取整 ✅x很大mid*mid在 Python 不会溢出大整数其他语言需防溢出为什么right x而不是x - 1x0时x-1-1会越界/跳过循环x1时x-10也边界紧张。用x覆盖[0, x]最安全。复杂度时间O(log x)每次区间减半空间O(1)只用几个变量易错点易错点错误写法正确mid公式left right // 2(left right) // 2mid位置在循环外算一次循环内每轮重算循环条件while left rightwhile left rightreturn位置写在循环里循环外返回值return leftreturn right右边界right x - 1right x比较mid xmid * mid x一句话记忆在[0, x]里二分mid*mid x就往右找leftmid1否则往左缩rightmid-1循环结束leftright1返回right即向下取整平方根。判断条件是「平方比较」不是「大小比较」。