演算法精講：兩個有序數組合併後的中位數 O(log(min(m,n))) 解法

情況一：等長數組 (m = n)

1. 比較 A[m/2] 與 B[n/2]。
2. 相等：即為中位數，直接返回。
3. A[mid] < B[mid]：中位數必在 A[mid...m-1] 與 B[0...mid] 之間。遞歸處理這兩個子數組。
4. A[mid] > B[mid]：對稱地，在 A[0...mid] 與 B[mid...n-1] 中遞歸。

遞歸基礎案例：當長度縮減至 1 或 2 時，直接暴力合併計算。

情況二：不等長數組 (m ≠ n)，假設 m ≤ n

關鍵洞見：每次遞歸拋棄 k = m/2 個元素，但需保證拋棄的元素總數不超過合併後左半部應有的數量。

比較 A[m/2] 與 B[n/2]：

① 相等 → 直接返回該值（無論奇偶長度皆成立）。

② A[m/2] < B[n/2]：
    中位數不在 A[0 ... m/2-1]（太小），也不在 B[n/2 ... n-1]（太大）。
    但不能直接丟棄 B[n/2 ... n-1] 全部，因為 B 可能比 A 長很多。
    正確丟棄：A[0 ... m/2-1] 以及 B[n - m/2 ... n-1]（對應長度 m/2）。
    新問題：在 A[m/2 ... m-1] (長 m/2) 和 B[0 ... n-m/2-1] (長 n-m/2) 中找中位數。

③ A[m/2] > B[n/2]：
    對稱丟棄 A[m/2 ... m-1] 和 B[0 ... m/2-1]，繼續遞歸。

複雜度分析

• 每次遞歸將較短數組長度減半：T(m) = T(m/2) + O(1)
• 時間複雜度：O(log m) = O(log(min(m,n)))
• 空間複雜度：遞歸棧深 O(log m)，可改寫迭代版達到 O(1)。

代碼骨架 (C++ 風格)

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if (A.size() > B.size()) return findMedianSortedArrays(B, A); // 確保 A 較短
    int m = A.size(), n = B.size();
    int left = 0, right = m, half = (m + n + 1) / 2;
    
    while (left <= right) {
        int i = (left + right) / 2; // A 的分割點
        int j = half - i;           // B 的分割點
        
        int Aleft  = (i == 0) ? INT_MIN : A[i-1];
        int Aright = (i == m) ? INT_MAX : A[i];
        int Bleft  = (j == 0) ? INT_MIN : B[j-1];
        int Bright = (j == n) ? INT_MAX : B[j];
        
        if (Aleft <= Bright && Bleft <= Aright) {
            // 找到正確分割
            if ((m + n) % 2) return max(Aleft, Bleft); // 奇數長度
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0; // 偶數
        } else if (Aleft > Bright) {
            right = i - 1; // A 分太多，左移
        } else {
            left = i + 1;  // A 分太少，右移
        }
    }
    return 0.0; // 不會執行到這裡
}

關鍵細節總結

• 邊界哨兵： 用 INT_MIN/MAX 處理分割點在邊緣的情況，統一邏輯。
• 分割點定義： i 表示 A 左側元素個數，j = half - i 保證左側總數正確。
• 收斂條件： Aleft <= Bright && Bleft <= Aright 即為完美分割。

這道題是「二分查找在隱性有序空間應用」的經典範例，掌握其分割不變量設計，對解決類似「兩數組第 K 小」等問題極有幫助。