模块三：二分——69.x的平方根

题目描述

题目链接：69.x的平方根

算法原理

解法一：暴力查找

依次枚举 [0, x] 之间的所有数 i （这⾥没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了，往后的情况就不会再判断。反⽽研究枚举区间，既耽误时间，⼜可能出错）

• 如果 i * i == x ，直接返回 x ；
• 如果 i * i > x ，说明之前的⼀个数是结果，返回 i - 1 。

由于 i * i 可能超过 int 的最⼤值，因此使⽤ long long 类型

解法二：二分查找

设 x 的平⽅根的最终结果为 index ，分析 index 左右两边区间数据的特点：

• [0, index] 之间的元素，平⽅之后都是⼩于等于 x 的；
• [index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。

因此可以使⽤⼆分查找算法。

代码实现

暴力查找

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
18

C++

class Solution {
public:
    int mySqrt(int x) {
        // 处理边界情况
        if (x < 1)
            return 0;
        // 二段性使用二分
        int left = 1, right = x;
        while (left < right) {
            // 防溢出
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Java

class Solution {
    public int mySqrt(int x) {
        // 细节
        if (x < 1)
            return 0;
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x)
                left = mid;
            else
                right = mid - 1;
        }
        return (int) left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16