二分查找的典型问题（二）：二分答案

前篇链接 这里二分答案的意思是：题目要我们找的是一个整数，并且这个整数我们知道它可能的最小值和最大值。此时，我们可以考虑使用二分查找算法找到这个目标值。

根据目标变量具有的单调性质编写判别函数。

方法一：暴力解法

方法一：暴力解法 我们看示例 2 ，输入 8 返回的是 2，这是因为 3 的平方等于 9 大于 8，因此「结果只保留整数的部分，小数部分将被舍去」。要求我们从 1 开始找，找到最后一个平方以后小于等于 x 的那个数。 我们假设 s 表示从 1 开始的那个数。

如果 s 平方以后小于 x ，暂时放过；如果 s 平方以后等于 x ，直接返回 s ；如果 s 平方以后大于 x ，说明 s - 1 是题目要求的，返回 s - 1 。

友情提示：不要忽视对暴力解法的思考，在面试和笔试中可以不实现暴力解法，但是对暴力解法的缺点和潜在的问题需要有一定的分析，过渡到优化解法会更自然。

public class Solution { // 暴力解法 public int mySqrt(int x) { // 特判 if (x <= 1) { return x; } for (int i = 1; i <= x; ++i) { if (i == x / i) { return i; } else if (i > x / i) { return i - 1; } } throw new IllegalArgumentException("参数出错"); } }

注意：如果判别条件写成 s * s == x ，会发生整型溢出，应该写成 s = x / s ，判别条件 s * s > x 也是类似这样写。 复杂度分析：

时间复杂度：O(x)，最坏情况下暴力解法会一直尝试到 x/2，O(x/2) = O(x)；空间复杂度：O(1)O(1)，只使用到常数个变量。

方法二：二分查找

通过对暴力解法的分析，我们知道了，需要返回最后一个平方以后小于等于 x 的数。使用二分查找的思路 2，关键在于分析那些数是我们不要的。

很容易知道，如果一个数的平方大于 x ，这个数就一定不是我们要找的平方根。于是，可以通过逼近的方式找到平方根。 错误代码：

class Solution { public int mySqrt(int x) { int left = 0; int right = x; while (left < right){ // 写完分支以后调整为向上取整 int mid = (left + right + 1) / 2; if (mid * mid > x) { // mid 以及大于 mid 的数一定不是解，下一轮搜索的区间为 [left, mid - 1] right = mid - 1; } else { left = mid; } } return left; } }

提交以后，系统提示： 我们看到是这个很大的数，根据暴力解法的经验可以断定，是在计算 mid * mid 的时候出错了， mid * mid 超出了整数能表达的最大值。为此可以做如下修改：mid > x / mid。

class Solution { public int mySqrt(int x) { int left = 0; int right = x; while (left < right){ // 写完分支以后调整为向上取整 int mid = (left + right + 1) / 2; if (mid > x / mid) { // mid 以及大于 mid 的数一定不是解，下一轮搜索的区间为 [left, mid - 1] right = mid - 1; } else { left = mid; } } return left; } }

但事实上，只要仔细想一想就知道，一开始右边界 int right = x; 没有必要设置这么大（他根本不会取到这个值）。只要设置成它的一半即可。但是有个数 0 例外，单独对它做判断即可。下面这样写，也把 1 的平方根是 1包括进去了。

class Solution { public int mySqrt(int x) { if (x == 0) { return 0; } int left = 1; int right = x / 2; while (left < right){ // 写完分支以后调整为向上取整 int mid = (left + right + 1) / 2; if (mid > x / mid) { // mid 以及大于 mid 的数一定不是解，下一轮搜索的区间为 [left, mid - 1] right = mid - 1; } else { left = mid; } } return left; } }