###### tags: `LeetCode` `Binary Search` `Hard`
# LeetCode #4 [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)
### (Hard)

給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出並返回這兩個正序數組的中位數。

限定時間複雜度為O(log(m+n))。

---


當總數為奇數時, 中位數為A(m1-1)與B(m2-1)中較大的, 而總數為偶數時, 中位數為兩個數字取平均, 此時左數不變, 而右數為A(m1)與B(m2)中較小者。

因此, 將左值設為0, 右值設為nums1的大小(必須確保nums1個數小於nums2個數), 使用二元搜尋找到合適的m1, 使得nums1[m1]略大於nums2[m2-1]。

---

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        const int n1=nums1.size(), n2=nums2.size();
        if(n1>n2)return findMedianSortedArrays(nums2, nums1);
        
        int k=(n1+n2+1)/2;
        int l=0, r=n1;
        while(l<r){
            int m1=l+(r-l)/2;
            int m2=k-m1;
            if(nums1[m1]<nums2[m2-1])l=m1+1;
            else r=m1;
        }
        
        const int m1=l, m2=k-l;
        int c1=max(m1<=0?INT_MIN:nums1[m1-1],
                   m2<=0?INT_MIN:nums2[m2-1]);
        if((n1+n2)%2)return c1;
        int c2=min(m1>=n1?INT_MAX:nums1[m1],
                   m2>=n2?INT_MAX:nums2[m2]);
        return (double)(c1+c2)/2;
    }
};