在两个长度相等的排序数组中寻找上中位数

import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] a1, int[] a2) {
             // write code here
        int m = a1.length;
        return findMedianinTwoSortedAray(a1, 0, m - 1, a2, 0, m - 1, m);

    }

    public int findMedianinTwoSortedAray(int[] a1, int l1, int r1, int[] a2, int l2, int r2, int k) {
        int m = r1 - l1 + 1;
        int n = r2 - l2 + 1;

        if (m == 0) return a2[l2 + k - 1];

        if (k == 1) return Math.min(a1[l1], a2[l2]);

        int i1 = l1 + Math.min(m, k / 2) - 1;

        int i2 = l2 + Math.min(n, k / 2) - 1;

        if (a1[i1] > a2[i2]) {
            return findMedianinTwoSortedAray(a1, l1, r1, a2, i2 + 1, r2, k - (i2 - l2) - 1);
        } else {
            return findMedianinTwoSortedAray(a1, i1 + 1, r1, a2, l2, r2, k - (i1 - l1) - 1);
        }
    }
}

思路：因为两有序数组长度相等，所以递增序列长度一定为偶数，只需考虑一种情况即可；
注意：(1, 2, 3, 4) (3, 4, 5, 6) 递增序列长度为 8， 不是 (1, 2, 3, 4, 5, 6), 有点坑

求解的过程与求解正序数组中的中位数类似：

1. 若 a1 为空，则在 a2 中寻找第 k 大的数即可；
2. 求出两数组中对应的 (k / 2), 若数组的长度小于 (k / 2) 的值，则取数组长度即可；
3. 判断两个中位数的大小，若 a1 > a2，则下次计算取 a2 的右半段和 a1， 若 a1 <= a2，则取 a1 的后半段和 a2；
4. 若 k == 1 时，返回此时两数组中的最小值，即为所求结果。