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

题目

题解：
二分法，如果两个数组各自的中位数相等，则这个就是整体的中位数
如果arr1[mid1]<arr2[mid2]，则arr1的[0,mid1)和arr2的(mid2,r2]都不可能是中位数，l1=mid1+(r1-l1+1)%2==0?1:0,r2=mid
反之,arr2的[0,mid1)和arr1的(mid2,r2]都不可能是中位数，l2=mid2+(r1-l1+1)%2==0?1:0,r1=mid

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        // write code here

        int l1=0,r1=arr1.size()-1,l2=0,r2=arr2.size()-1;
        while(l1<r1)
        {
            int m1=(l1+r1)/2;
            int m2=(l2+r2)/2;
            int ofs=(r1-l1+1)%2==0?1:0;
            if(arr1[m1]==arr2[m2])return arr1[m1];
            else if(arr1[m1]<arr2[m2])
            {
                l1=m1+ofs;
                r2=m2;
            }
            else
            {
                l2=m2+ofs;
                r1=m1;
            }
        }
        return min(arr1[l1],arr2[l2]);

    }
};