69.x的平方根
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l,r,ans = 0,x,-1
while l <= r:
mid = (l+r)//2
if mid*mid <= x:
ans = mid
l =mid + 1
# 能找到的mid*mid <= x 的最小值，<= target, 然后不断轮着，右边边界减1，直到遍历之后退出
else:
r =mid - 1
return ans
代码解释：求平方根（整数部分）
这段代码使用 二分查找 来计算非负整数 x 的平方根的 整数部分（即向下取整）。例如：
mySqrt(4)返回2（因为2² = 4）mySqrt(8)返回2（因为2² = 4 < 8，而3² = 9 > 8）
关键变量：
l：左边界（初始为0）r：右边界（初始为x）ans：存储当前满足mid² ≤ x的最大mid（初始为-1）
算法流程：
- 初始化：
l = 0，r = x，ans = -1。 - 循环条件：
while l <= r，只要搜索范围有效（左边界 ≤ 右边界），就继续查找。 - 计算中间值：
mid = (l + r) // 2（取中间位置）。
- 比较
mid²和x：- 如果
mid² ≤ x：- 说明
mid可能是平方根的整数部分，记录ans = mid。 - 尝试找更大的
mid，调整l = mid + 1（向右搜索）。
- 说明
- 如果
mid² > x：- 说明
mid太大，调整r = mid - 1（向左搜索）。
- 说明
- 如果
- 循环结束：
- 返回
ans（即最大的满足mid² ≤ x的整数）。
- 返回
具体例子
示例 1：x = 4
查找过程：
-
初始状态：
l = 0,r = 4,ans = -1
-
第 1 轮循环：
mid = (0 + 4) // 2 = 22² = 4 ≤ 4→ans = 2,l = 3- 新的搜索范围：
l = 3,r = 4
-
第 2 轮循环：
mid = (3 + 4) // 2 = 33² = 9 > 4→r = 2- 新的搜索范围：
l = 3,r = 2（不满足l <= r，循环终止）
结果：ans = 2（因为 2² = 4 是 4 的平方根）。
示例 2：x = 8
查找过程：
-
初始状态：
l = 0,r = 8,ans = -1
-
第 1 轮循环：
mid = (0 + 8) // 2 = 44² = 16 > 8→r = 3- 新的搜索范围：
l = 0,r = 3
-
第 2 轮循环：
mid = (0 + 3) // 2 = 11² = 1 ≤ 8→ans = 1,l = 2- 新的搜索范围：
l = 2,r = 3
-
第 3 轮循环：
mid = (2 + 3) // 2 = 22² = 4 ≤ 8→ans = 2,l = 3- 新的搜索范围：
l = 3,r = 3
-
第 4 轮循环：
mid = (3 + 3) // 2 = 33² = 9 > 8→r = 2- 新的搜索范围：
l = 3,r = 2（不满足l <= r，循环终止）
结果：ans = 2（因为 2² = 4 < 8，而 3² = 9 > 8）。
示例 3：x = 1
查找过程：
-
初始状态：
l = 0,r = 1,ans = -1
-
第 1 轮循环：
mid = (0 + 1) // 2 = 00² = 0 ≤ 1→ans = 0,l = 1- 新的搜索范围：
l = 1,r = 1
-
第 2 轮循环：
mid = (1 + 1) // 2 = 11² = 1 ≤ 1→ans = 1,l = 2- 新的搜索范围：
l = 2,r = 1（不满足l <= r，循环终止）
结果：ans = 1（因为 1² = 1 是 1 的平方根）。