筆記: 【演算法新手村】[初階]筆記03 - 二分練習題

題目翻譯(by Gemini)

給定一個非負整數 x，回傳 x 的算術平方根，並無條件捨去至最接近的整數。
回傳的整數也必須是非負的。
限制條件：你不得使用任何內建的指數函數或運算子。（例如：不可使用 C++ 中的 pow(x, 0.5) 或 Python 中的 x**0.5。）

• 範圍 0 <= x <= 2³¹ - 1

解題思路

這題主要有兩種方式：二分搜尋跟牛頓法
這邊我以二分搜尋為主，這邊還是一樣先解釋一下為甚麼可以用
因為 x 的平方根一定落在 0 到 x 之間，且這個區間是有序的，所以我們可以用二分搜尋來逼近答案
(也就是尋找一個整數 m，使得 m² ≤ x 且 (m+1)² > x)。

題目已經給了我們x的範圍，我們其實可以直接濃縮出答案的範圍進行搜尋，當然也可以直接按照題目的範圍去搜，這邊以題目給的範圍為例，最小是0，可以得出 l = 0；最大是int類型的最大值，可以得出 r = INT_MAX，之後取中值進行查詢，檢查如果m×m ≤ x就紀錄並且繼續向右進行查詢，反之則代表目前太大要向左查詢，當然這邊需要注意溢出問題：乘法極其容易超出int範圍，我們可以改用除法進行等效替換，或者直接使用long long(最簡單暴力省時省力)。

這邊討論一下加法的溢位問題，這邊其實直接寫 m = (l+r)/2 也不會出錯，因為一開始的值會是IMT_MAX / 2，而值域(答案會出現的集合)的最大值比這個還小，所以第一次一定會是 r = mid-1 執行，這才避免了溢位問題，反之如果答案有可能出現在IMT_MAX / 2~IMT_MAX這個區間，我們如果直接使用m = (l+r)/2就會出錯，這個需要注意一下。

INT_MAX是從C就有的，包含在<limits.h>裡面，C++則在<climits>裡面。
以下提供幾種替換：1e9：靠近INT_MAX但比其小，但是遠大於這題的值域最大值，所以也可以使用。
std::numeric_limits<int>::max()：C++現代化寫法、樣板風格，包含在<limits>中
(leetcode中都可以不用手動引入這些庫)

程式碼實作 (C++)

class Solution {
public:
    int mySqrt(int x) {
        int l = 0 , r = INT_MAX;
        int ans = -1;
        int m;

        while(l <= r){
            m  = l + (r - l) / 2;
            if(m == 0){
                ans = m;
                l = m+1;
            }
            else{
                if(m <= x/m){
                    ans = m;
                    l = m+1;
                }
                else{
                    r = m-1;
                }            
            }
        }
        return ans;
    }
};

C的code也是幾乎相同，略。