69. Sqrt(x)

題目網址：https://leetcode.cn/problems/sqrtx/

題意：給一非負整數 x, 計算並返回 x 的平方根 。

由於返回類型是整數, 因此答案只保留整數部分, 小數部分將被捨棄。

注意：禁止使用 pow(x, 0.5) or x ** 0.5 運算。

Solution：

想法：利用 Binary Search, 左閉右開容易導致 overflow。當 x = INT_MAX 時, x + 1 會 overflow, 故要先將 x 轉成 long

class Solution {
public:
    int mySqrt(int x) {
        int left = 0, right = x;

        while (left <= right) {
            // mid 轉成 long, 避免 mid * mid 出現 overflow
            const long mid = left + (right - left) / 2;

            if (mid * mid > static_cast<long>(x)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left - 1; // left 的平方 > mid, 所以 left - 1 的平方 ≤ mid
    }
};

• time：$O(log(x))$ ➔ Binary Search
• space：$O(1)$ ➔ 只需常數空間