【算法】二分算法——x的平方根

本节博客使用“二分边界算法”对“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;
      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

其中有需要代码细节，想要知道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;
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：当然还可以把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;
      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.总结

说实在的掌握了二分边界算法这个题不难，但是就是我第四步那个细节问题要注意！！！我就被坑了~

---

EOF