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

#include <functional>
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) {
        int n = arr1.size();
        function<int(int, int, int, int, int)> findMedianinTwoSortedAray2 = [&](int l1, int r1, int l2, int r2, int k) -> int {
            if (l1 > r1) {
                return arr2[l2 + k - 1];
            }
            if (l2 > r2) {
                return arr1[l1 + k - 1];
            }
            if (k == 1) {
                return min(arr1[l1], arr2[l2]);
            }
            int m1 = l1 + min(r1 - l1 + 1, k / 2) - 1;
            int m2 = l2 + min(r2 - l2 + 1, k / 2) - 1;
            if (arr1[m1] < arr2[m2]) return findMedianinTwoSortedAray2(m1 + 1, r1, l2, r2, k - (m1 - l1 + 1));
            return findMedianinTwoSortedAray2(l1, r1, m2 + 1, r2, k - (m2 - l2 + 1));
        };
        return findMedianinTwoSortedAray2(0, n - 1, 0, n - 1, n);
    }
};

思路：二分查找。

每次二分可以排除其中一个数组一半的元素。