# 「力扣」第 69 题：x 的平方根（简单）
# 题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1：
输入：4
输出：2
示例 2：
输入：8
输出：2
说明：8 的平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。
提示：
# 题意分析
- 这道题要求我们实现平方根函数，输入是一个非负整数，输出也是一个整数；
- 但是题目当中说：结果只保留整数的部分，小数部分将被舍去。这是什么意思呢？我们分析一下示例。
示例 1：
输入: 4
输出: 2
这是显然的，
示例 2 ：
输入: 8
输出: 2
因为
# 思路分析
从题目的要求和示例我们可以看出，这其实是一个查找整数的问题，并且这个整数是有范围的。
- 如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
- 如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；
- 如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
因此我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。
- 猜的数平方以后大了就往小了猜；
- 猜的数平方以后恰恰好等于输入的数就找到了；
- 猜的数平方以后小了，可能猜的数就是，也可能不是。
很容易知道，题目要我们返回的整数是有范围的，直觉上一个整数的平方根肯定不会超过它自己的一半，但是
参考代码：
public class Solution {
public int mySqrt(int x) {
// 特殊值判断
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x / 2;
// 在区间 [left..right] 查找目标元素
while (left < right) {
int mid = left + (right - left + 1) / 2;
// 注意：这里为了避免乘法溢出，改用除法
if (mid > x / mid) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
return left;
}
}
复杂度分析：
- 时间复杂度：
，每一次搜索的区间大小约为原来的 ，时间复杂度为 ； - 空间复杂度：
。
对代码编写逻辑的解释：
一、写 if 和 else 的原因：
- 猜的数是
mid，根据上面的分析，如果mid的平方 严格大于x，mid肯定不是解，比mid大的整数也肯定不是解，因此问题的答案只可能存在区间[left..mid - 1]，此时设置right = mid - 1； else的情况就是if的反面，只要if的分支和对应的区间分析对了，else的区间是[left..mid - 1]的反面区间，即[mid..right]，此时设置left = mid。
二、为什么最后返回 left。
- 退出
while (left < right)循环的时候，由于边界搜索是left = mid与right = mid - 1，因此退出循环的时候一定有left与right重合，返回right也可以。
# 问题：mid 为什么要加 1？
对着错误的测试用例打印出变量 left 、right 和 mid 的值看一下就很清楚了。
mid 不加 1 会造成死循环的代码：
public class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
if (x == 1) {
return 1;
}
int left = 1;
int right = x / 2;
// 在区间 [left..right] 查找目标元素
while (left < right) {
// 取中间数 mid 下取整时
int mid = left + (right - left) / 2;
// 调试语句开始
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("left = " + left + ", right = " + right + ", mid = " + mid);
// 调试语句结束
// 注意：这里为了避免乘法溢出，改用除法
if (mid > x / mid) {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间是 [mid..right]
left = mid;
}
}
return left;
}
public static void main(String[] args) {
Solution solution = new Solution();
int x = 9;
int res = solution.mySqrt(x);
System.out.println(res);
}
}
控制台输出：
left = 1, right = 4, mid = 2
left = 2, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
left = 3, right = 4, mid = 3
在区间只有 if、else 的逻辑区间的划分方式是：[left..mid - 1] 与 [mid..right]。如果 mid 下取整，在区间只有 mid 的值等于 left，一旦进入分支 [mid..right] 区间不会再缩小，出现死循环。
解决办法：把取中间数的方式改成上取整。
作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-2/0069-sqrtx 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。