题解 | #在两个长度相等的排序数组中找到上中位数#

核心思想：
设i+j+2=N
假设中位数是arr1[i]与arr2[j]中的一个,那么必然满足以下2个充分必要条件
1:arr1[i]<=arr2[j+1]
2:arr2[j]<=arr1[i+1]

充分性：
由i+j+2=N得,arr1[0~i]与arr2[0~j]共有N个数字，（总数2N）
由条件1得，arr1[0~i]<=arr2[j+1~N-1]，又因为arr1递增，arr1[0~i]<=arr1[i+1~N-1]
由条件2得，arr2[0~j]<=arr1[i+1~N-1]，又因为arr1递增，arr2[0~j]<=arr2[j+1~N-1]
所以arr1[0~i]与arr2[0~j]构成了较小的N个数字。
所以中位数是arr1[0~i]与arr2[0~j]中最大的数
又因为递增
所以中位数是arr1[i]与arr2[j]中的一个

必要性：
不妨设arr1[i]是中位数，那么arr2[j]<=arr1[i]。
因为arr2[j]<=arr1[i]，arr1递增
所以条件2：arr2[j]<=arr1[i+1]成立

假设arr1[i]>arr2[j+1]
那么至少有N个数字小于arr1[i]，与arr1[i]是中位数矛盾
所以条件1：arr1[i]<=arr2[j+1]成立

然后只要用二分的方法去搜索i就可以了

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int get(vector<int>&arr ,int idx){
        if (idx<0)
            return -1;
        if (idx>=arr.size())
            return 0x7fffffff;
        return arr[idx];
    }
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int N = arr1.size();
        int l=0,r=N-1;
        while(l<=r){
            int mid1=(l+r)/2;
            int mid2 = N-2-mid1;
            if(get(arr1,mid1)<=get(arr2,mid2+1)&&get(arr2,mid2)<=get(arr1,mid1+1))
                return max(arr1[mid1],arr2[mid2]);
            else if(get(arr1,mid1)>get(arr2,mid2+1))
                r=mid1-1;
            else
                l=mid1+1;
        }
        return -1;//this line will not be used

    }
};