4. 寻找两个正序数组的中位数

难度：🔴 Hard | 标签：二分查找、分治 | 状态：⬜ LeetCode 链接

思路

要求 O(log(m+n))。 在较短数组上二分切分点 i，对应另一数组切分点 j = (m+n+1)/2 - i。 要求 A[i-1] <= B[j] 且 B[j-1] <= A[i]。

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
        if (A.size() > B.size()) return findMedianSortedArrays(B, A);
        int m = A.size(), n = B.size();
        int total = (m + n + 1) / 2;
        int l = 0, r = m;
        while (l <= r) {
            int i = l + (r - l) / 2;
            int j = total - i;
            int Al = i == 0 ? INT_MIN : A[i - 1];
            int Ar = i == m ? INT_MAX : A[i];
            int Bl = j == 0 ? INT_MIN : B[j - 1];
            int Br = j == n ? INT_MAX : B[j];
            if (Al <= Br && Bl <= Ar) {
                if ((m + n) % 2) return max(Al, Bl);
                return (max(Al, Bl) + min(Ar, Br)) / 2.0;
            }
            if (Al > Br) r = i - 1;
            else l = i + 1;
        }
        return 0.0;
    }
};

复杂度

• 时间 O(log min(m, n))，空间 O(1)

易错 / 回顾

• 保证短的数组做二分，避免 j 越界
• INT_MIN / INT_MAX 兜底两端
• 奇偶分情况：奇数取 max(Al, Bl)；偶数取 (max + min) / 2.0
• 难题，能讲清思路即可，不强求一次手写 AC