LeetCode Median of Two Sorted Arrays：分治法 O(log(m+n)) 尋找第 k 小元素

問題轉化

兩個已排序數組 A(m)、B(n)，求合併後的中位數。等價於找第 k = (m+n)/2 小元素（奇數情況）或前兩者平均（偶數情況）。要求 O(log(m+n)) 時間。

分治核心思想

比較 A[k/2-1] 與 B[k/2-1]（兩數組各自的第 k/2 小元素）：

• 若 A[k/2-1] < B[k/2-1] → A 前 k/2 個元素不可能是第 k 小，遞歸在 A[k/2...] 和 B 中找第 k - k/2 小
• 若 > → 同理捨棄 B 前 k/2 個
• 若 = → 直接返回該值（理想情況）

邊界條件處理

1. 某數組為空 → 直接返回另一數組第 k 小
2. k=1 → 返回兩數組首元素較小者
3. 數組長度 < k/2 → 取實際長度作為 pa，pb = k - pa

標準實現

double findKth(int A[], int m, int B[], int n, int k) {
    if (m > n) return findKth(B, n, A, m, k); // 保證 m ≤ n
    if (m == 0) return B[k-1];
    if (k == 1) return min(A[0], B[0]);
    int pa = min(k/2, m), pb = k - pa;
    if (A[pa-1] < B[pb-1])
        return findKth(A+pa, m-pa, B, n, k-pa);
    else if (A[pa-1] > B[pb-1])
        return findKth(A, m, B+pb, n-pb, k-pb);
    else return A[pa-1];
}

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m + n;
        if (total & 1) return findKth(A, m, B, n, total/2 + 1);
        return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total/2 + 1)) / 2.0;
    }
};

參考資源

詳細推導可參考：CSDN 經典講解

複雜度證明

每次遞歸 k 減少約一半，遞歸深度 O(log k) = O(log(m+n))。每層 O(1) 操作，總體 O(log(m+n))，完美滿足要求。