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

[utterances-bot]

0004. 寻找两个正序数组的中位数 | 算法通关手册

4. 寻找两个正序数组的中位数 # 标签：数组、二分查找、分治算法 难度：困难 题目大意 # 描述：给定两个正序（从小到大排序）数组 nums1、nums2。

https://algo.itcharge.cn/Solutions/0001-0099/median-of-two-sorted-arrays/

[S1mpleBug]

附上C++版本

按照上述题解含义，找到中位线很关键，可通过二分对中位线进行划分。剩下的各种情况的讨论可观看官方题解，说的很明白。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if(n1 > n2)
            return findMedianSortedArrays(nums2, nums1);
        // n1 <= n2
        int k = n1 + ((n2-n1+1)>>1);
        int l = 0, r = n1;
        while(l < r) {
            int mid = l + ((r-l+1)>>1);
            if(nums1[mid-1] > nums2[k-mid]) r = mid-1;
            else l = mid;
        }
        //l是中位线在第一个数组中左侧的位置
        //k-l是中位线在第二个数组中左侧的位置
        
        int leftMax1 = l==0 ? INT_MIN : nums1[l-1];
        int rightMin1 = l==n1 ? INT_MAX : nums1[l];
        int leftMax2 = k-l==0 ? INT_MIN : nums2[k-l-1];
        int rightMin2 = k-l==n2 ? INT_MAX : nums2[k-l];

        int t = max(leftMax1, leftMax2);
        if((n1+n2)%2 == 1) return (double)t;
        return (double)(t+min(rightMin1,rightMin2))/2.0;
    }
};

• 官方题解视频链接🔗