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

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
        // 直接挑战进阶版本的时间和空间复杂度，这个时间复杂度只能靠二分了
        // 如果最开始的数编号就是 1
        // 仔细看题目，两个数组长度都是 N，上中位数就是两个数组合并且排序之后第 N 个数
        // 不要直接合并数组，有索引就够了
        // 二分的话设置左右边界，然后在 arr1 里设置一个 cut1，
        // arr2 里设置一个 cut2 = N - cut1，这样保证这两个下标左边的数正好是 N 个
        // 找上中位数的话肯定不小于左边的数，不大于右边的数，这个就是我们调整 cut1 的条件
        int n = arr1.size();
        int low = 0, high = n;
        
        while (low < high) {
            int cut1 = (low + high) / 2;
            int cut2 = n - cut1;

            int left1 = (cut1 == 0) ? INT_MIN : arr1[cut1 - 1];
            int left2 = (cut2 == 0) ? INT_MIN : arr2[cut2 - 1];
            int right1 = (cut1 == n) ? INT_MAX : arr1[cut1];
            int right2 = (cut2 == n) ? INT_MAX : arr2[cut2];

            if (left1 <= right2 && left2 <= right1) {
                // C++ 数组最开始编号是 0，按照定义是 n - 1 这个位置是上中位数
                return max(left1, left2);
            } else if (left1 > right2) {
                // cut1 位置靠右了，往左边调一点
                high = cut1;
                cout << "high = " << high << endl;
            } else {
                // cut1 位置靠左了，往右边调一点
                low = cut1 + 1;
                cout << "low = " << low << endl;
            }
        }
        // 上面的代码在处理诸如 [1,2],[3,4] 这样两个数组直接拼一起都是递增的输入会有问题，
        // low 一直加加到和 n 一样大也没办法满足 left1 <= right2 && left2 <= right1
        if (low == n) return arr1[n - 1];
        // 只是为了让函数编译通过，通常来说不会在这里 return，不然就是前面代码写的有问题
        return -1;
    }
};