【LeetCode69.x的平方根】——二分查找_x的平方根-二分查找

69.x的平方根：

你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留整数部分 ，小数部分将被 舍去 。注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
链接：https://leetcode.cn/problems/sqrtx

示例 1:

输入：x = 4
输出：2  
1
2

示例 2:

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。      
1
2
3

提示：

• 0 <= x <= 231 - 1

初步思考：（二分查找）

关键词：只保留整数部分。

这就给我们带来了思路，求解的整数ans满足表达式ans*ans<=x，因而我们可以将x前的数看作是一个数组，进行二分查找进而获得答案。

这里使用的是左开右开形二分查找：

左开右开：

int mySqrt(int x) {
        int left = 0;//考虑0的情况
        int right = x / 2 + 2; //考虑1的情况
        while (left + 1 != right)
        {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) //使用除法避免溢出（乘法会溢出）
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

利用左开右开区间的好处在于：不同特地再去讨论x=0或x=1的特殊情况。同时，该题也很容易出现内存溢出的问题，所以此处采用了用除法代替乘法的方式，防止内存溢出。

该算法的执行用时出奇得低。

当然，该题同样可以使用左闭右闭以及左闭右开的二分查找进行求解。

左闭右开：

int mySqrt2(int x) {
        // 先对特殊值进行判断
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        int left = 1;
        int right = x / 2;
        // 左闭右开
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (mid > x / mid) {
                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

进一步思考：（数学方法）

在LeetCode官方题解中还有着两种数学方法的求解方式，这里就不多加介绍，比较主要使用的数学公式以及方法，属于一种聪明的暴力求解法。

这部分代码来源于LeetCode题解：

链接：https://leetcode.cn/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/

指数算法：

 int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
1
2
3
4
5
6
7

该种算法的时间复杂度以及空间复杂度都可以视作为O（1），但是运用了内置的个exp函数以及log函数

牛顿迭代法：

借助了泰勒级数，从初始值开始快速向零点逼近。

int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总的来说，该题的难点在于发现题目中的要求是取整数值，进而可以想到运用二分查找的方法进行求解。
以后也会坚持持续更新的我LeetCode学习笔记，分享我所学到的以及我个人的思考，欢迎和我一起来交流。