题目
题目要求非负整数 x 的平方根，相当于求函数 y = √x 中 y 的值，函数 y = √x 图像如下：
从上图中，可以看出函数是单调递增的，满足二分查找的条件（区间是有序的），所以可以考虑用二分查找去做。
解题细节
1、由于当 x 为非负整数时，其平分根一定在区间 [1, x/2 1] 内，所以为了缩小查找的范围，二分的左右边界分别取 left = 1 和 right = x / 2 1，而不分别取 0 和 x；
2、为了防止在查找过程中比较 mid * mid 和 x 中前者值太大，超出整型范围而溢出，取 mid 与 x / mid 进行比较（mid 为 解题细节 1 中 的 left 和 right 的和的平均值，故不会等于 0）。
Show me the Code
代码语言：javascript复制// C 语言版本
int mySqrt(int x){
int left = 1, right = x / 2 1;
while (left <= right) {
/* 防止溢出 */
int mid = left ((right - left) >> 1);
/* mid 大于 √x ，在 mid 前半区间查找 */
if (mid > x / mid) {
right = mid - 1;
/* mid 小于 √x ，在 mid 后半区间查找 */
} else if (mid < x / mid) {
left = mid 1;
/* mid 等于 √x ，查找到直接返回 */
} else if (mid == x / mid) {
return mid;
}
}
return right;
}
# python3 版本
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 1, x/2 1
while l <= r:
m = (l r) // 2
if m > x / m:
r = m - 1
elif m < x / m:
l = m 1
else:
return int(m)
return int(r)说明
- right = x / 2 1，而不是 right = x / 2，因为当 x = 1 时，如果 right 取 x / 2 的话，由于 x/2 = 0，此时 left = 1 大于 right，直接循环跳出，导致 x 的平方根为 0 而不是 1 出错；
- 最后是 return right 还是 return left，可以通过调试得出，循环退出的条件是 left = right 1，当 x = 8 的时候，题目要求返回的是 2 ，如果最后是 return left 的话，返回的结果是 3 ，所以返回的是 right 。
