[NC]396. 求立方根

🚩传送门：牛客题目

题目

给定一个非负整数 ，计算并返回 的立方根，即实现 函数。

要求：如果立方根不是整数，输出只保留整数的部分，小数部分将被舍去。

示例 1:

输入: x = 9 输出: 3

解题思路：二分法

对于非负整数 可以暴力搜索其正数平方根。从 开始，计算当前值 是否满足

• 成立就输出结果
• 不成立计算下一个值 ++ 继续判断。

暴力解法的时间复杂度为 。

🚩这个过程其实可以使用 二分法优化 ，因为根据数学知识可知数字的平方根一定在区间，取这个区间的中间值，并判断与的大小关系。

• 若 ，接着判断 。

  - 如果满足  ![](https://cdn.nlark.com/yuque/__latex/5d9eea9dce1fe9f6c9690dae5a11414e.svg#card=math&code=%5Csmall%20%20%28m%20%2B%201%29%5E%203%20%3E%20n%0A%0A&id=Tuw7U)，那么![](https://cdn.nlark.com/yuque/__latex/4760e2f007e23d820825ba241c47ce3b.svg#card=math&code=m&id=i9Hpd)就是![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=dbSnT)的平方根。
  - 如果满足 ![](https://cdn.nlark.com/yuque/__latex/4fdde7bc7e8eb1490e4d1ca6633ba02d.svg#card=math&code=%5Csmall%20%20%28m%20%2B%201%29%5E%203%20%5Cleq%20n%0A%0A&id=XZ8V3)，则![](https://cdn.nlark.com/yuque/__latex/df378375e7693bdcf9535661c023c02e.svg#card=math&code=n&id=fkvYb)的平方根比![](https://cdn.nlark.com/yuque/__latex/4760e2f007e23d820825ba241c47ce3b.svg#card=math&code=m&id=i0b8X)大，继续搜索 `**[m + 1, n]**`。

• 若 ，则说明的平方根比小，继续搜索 **[1, m - 1]**。

我的代码

public class Solution {
    public int cuberoot(int x) {
        int left = 1;
        int right = x;
        while (left <= right) {
            // 1.不可使用 (left+right)/2 原因:left+right 可能溢出int
            int mid = left + ((right - left) >> 1);
            // 2.不可使用 mid*mid  原因:mid*mid 可能溢出int
            if (mid <= x / mid / mid) {
                if (mid + 1 > x / (mid + 1) / (mid + 1)) {
                    return mid;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return 0;
    }
}