题解 | #在两个长度相等的排序数组中找到上中位数#（二分查找寻找）

class Solution {
public:
    /*
    有序数组 中位数
    二分查找
    1.两个数组中间数相同，合并后，中位数一定是该数
    2.arr1的中位数比arr2 的中位数小则 合并后，中位数一定在arr1的右区间和arr2 的左区间
    3.同理arr2的中位数比arr1 的中位数小则 合并后，中位数一定在arr2的右区间和arr1的左区间
    ps:当时数组长度为偶数时，需要对去除左区间的数组中位数指针移动一位，指向另外一半。
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        if(n == 0)return NULL;
        int l1 = 0, r1 = n - 1;
        int l2 = 0, r2 = n - 1;
        int mid1 = 0, mid2 = 0, even = 0;
        while(l1 < r1){
            even = (r1 - l1)%2; // 是否是偶数个
            mid1 = l1 + r1 >> 1; // arr1中位数
            mid2 = l2 + r2 >> 1;// arr2中位数
            if(arr1[mid1] == arr2[mid2]) return arr1[mid1]; // 两个数组中间数相同，合并后，中位数一定是该数
            else if(arr1[mid1] < arr2[mid2]){  // arr1 中位数比 arr2小
                l1 = mid1 + even;
                r2 = mid2;
            }
            else{  // arr2 中位数比 arr1小
                l2 = mid2 + even;
                r1 = mid1;
            }
        }
        return min(arr1[l1], arr2[l2]); // 得到的两个数取中位数，即最小一个就是
    }
};