LeetCode 4：兩個有序數組的中位數——O(log(m+n)) 二分查找解法

題目描述

給定兩個已排序數組 nums1、nums2，長度分別為 m、n。找出這兩個數組合併後的中位數，要求時間複雜度 O(log(m+n))。

核心思路：轉化為尋找第 k 小元素

中位數即合併數組中第 k 小元素（或前兩個元素平均）。利用二分查找，每次排除 k/2 個不可能的元素：

• 比較 nums1[k/2-1] 與 nums2[k/2-1]。
• 較小者及其之前的元素必定小於第 k 小元素，可直接捨棄。
• 遞歸處理剩餘子數組與更新後的 k。

C++ 參考實現

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

private:
    int findKth(const vector<int>& A, int i, const vector<int>& B, int j, int k) {
        if (i >= A.size()) return B[j + k - 1];
        if (j >= B.size()) return A[i + k - 1];
        if (k == 1) return min(A[i], B[j]);

        int step = k / 2;
        int aVal = (i + step - 1 < A.size()) ? A[i + step - 1] : INT_MAX;
        int bVal = (j + step - 1 < B.size()) ? B[j + step - 1] : INT_MAX;

        if (aVal < bVal)
            return findKth(A, i + step, B, j, k - step);
        else
            return findKth(A, i, B, j + step, k - step);
    }
};

關鍵點

• 處理數組越界：用 INT_MAX 填充，保證另一數組元素被優先選擇。
• 終止條件：k==1 直接返回較小值；某數組耗盡直接返回另一數組對應位置。
• 奇偶長度統一：left、right 分別對應中位數左/右索引，偶數取平均，奇數兩者相同。

複雜度

• 時間：每次遞歸排除 k/2 元素，深度 O(log(m+n))。
• 空間：遞歸棧深度 O(log(m+n))，可改寫迭代版本達到 O(1)。