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

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
        if(arr1.size() == 1) return min(arr1[0], arr2[0]); // 特判
        int n = arr1.size(); // 记录一下递增序列的长度
        int l1 = 0, r1 = n - 1, l2 = 0, r2 = n - 1; // 记录一下两个序列的左右端点
        int mid1 = 0, mid2 = 0, even = 0; // 记录两个序列的中点、以及序列长度是否为奇偶数
        while(l1 < r1) {
            even = (r1 - l1) % 2; // arr1长度为奇数even数值为0，为偶数数值为1
            mid1 = (l1 + r1) / 2;
            mid2 = (l2 + r2) / 2;
            if(arr1[mid1] == arr2[mid2]) return arr1[mid1]; // 当两个序列的中位数相等，返回中位数
            else if(arr1[mid1] < arr2[mid2]) { // 当出现不等情况，取较小区间的右半部分和较大区间的左半部分
                l1 = mid1 + even; // 长度为偶数子区间，因为是mid是靠下取值，所以要加1作为右区间起点
                r2 = mid2;
            }
            else {
                l2 = mid2 + even;
                r1 = mid1;
            }
        }
        cout << "l1: " << l1 << " " << "l2: " << l2 << endl;
        return min(arr1[l1], arr2[l2]);
    }
};