分析

• 本题的考点：二分。

• 答案区间一定在[0, x]之间，每次取中间数mid，如果$mid ^ 2 \le x$，说明答案一定在[mid, x]之间，否则答案在[0, mid-1]之间。

代码

• C++

class Solution {
public:
    int mySqrt(int x) {

        int l = 0, r = x;
        while (l < r) {
            int mid = l + 1ll + r >> 1;  // 防止越界
            if (mid <= x / mid) l = mid;  // 防止越界
            else r = mid - 1;
        }
        return r;
    }
};

• Java

class Solution {
    public int mySqrt(int x) {

        int l = 0, r = x;
        while (l < r) {
            int mid = (int)((long)l + r + 1 >> 1);  // 防止越界
            if (mid <= x / mid) l = mid;  // 防止越界
            else r = mid - 1;
        }
        return r;
    }
}

时空复杂度分析

• 时间复杂度：$O(log(x))$。

• 空间复杂度：$O(1)$。