本节博客使用“二分边界算法”对“x的平方根”这一题目进行求解，有需要借鉴即可。
1.题目
题目链接：LINK
2.暴力求解
暴力求解思路：
这个题目可以用暴力求解来做，无非是从0到x的平方挨个试一下，如果是>目标值，就返回前一个数字，小于目标值，测试下一个值，等于目标值就返回该值就可以了。
假设测试数字用num来表示，其平方用num^2来表示
- num^2 > x 返回num-1
- num^2 = x 返回num
- num^2 < x 继续测试num+1
显然这个题目还有更优秀的方法，就是用二分算法。
不过二分算法是怎么想到的并且是怎么进行思考的呢？下面来进行细说：
3.二分算法求解
我们在暴力求解中，无非是从0^2 ,1^2 ,2^2… , x^2…所以说也可以根据是否其平凡大于还是小于等于目标值来做划分，这就满足了我们二分算法的使用前提条件：数组具有“二段性”。
那我们可以将0~x值划分为两部分：
- n^2 <= x
- n^2 > x
思考：为什么要将数组划分为n^2 <= x；n^2 > x。
换言之，为什么不用n^2 < x;n^2 >= x来做划分呢？？？
答：因为大于x的num值绝对不可能是最终返回结果，而小于x的值有可能是最终返回结果，等于x的值一定是返回结果(有可能没有这个整数值)
根据上面思想，我们可以将整个数组划分为下面这种情况：
那么，我们具体的代码逻辑也可以得出：
- mid*mid <= x —> left = mid;
- mid*mid > x —> right = mid - 1;
依照上面分析，我们可以写出示例代码：
class Solution { public: int mySqrt(int x) { int left = 0, right = x; while (left < right) { long long mid = left + (right - left + 1) / 2; if (mid * mid > x) { right = mid - 1; } else { left = mid; } } return left; } };
其中有需要代码细节，想要知道mid取值为什么是这样以及left和right的if逻辑可以点击链接：LINK
当然，上面这个代码有点小问题哈，在leetcode是过不了的：
4.取值范围细节
在做题的时候要注意读题目中的取值范围：
题目中提示说，这个x取值范围是0到int_max值，但是我们mid计算时候，用到的是long long mid = left + (right - left + 1) / 2;这个表达式会先根据left、right类型(int)生成一个临时int变量来生成结果值赋给mid，但是在计算时候，right - left + 1 = int_max + 1这样就int临时变量溢出了，自然会报错，不过只有给的x是int_max时才会出现这个错误
所以我们可以修改一下，
方法一：是把x = 0进行特殊处理，让left从1开始right - left少一个数字
比如代码：
class Solution { public: int mySqrt(int x) { // 由于两个较⼤的数相乘可能会超过 int 最⼤范围 // 因此⽤ long long long long i = 0; for (i = 0; i <= x; i++) { // 如果两个数相乘正好等于 x，直接返回 i if (i * i == x) return i; // 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数 if (i * i > x) return i - 1; } // 为了处理oj题需要控制所有路径都有返回值 return -1; } };
方法二：当然还可以把int left类型改为long来处理。
class Solution { public: int mySqrt(int x) { long left = 0, right = x; while (left < right) { long long mid = left + (right - left + 1) / 2; if (mid * mid > x) { right = mid - 1; } else { left = mid; } } return left; } };
5.总结
说实在的掌握了二分边界算法这个题不难，但是就是我第四步那个细节问题要注意！！！我就被坑了~
EOF
