/**
 * Created by tlh on 2017/5/17.
 * 求两个排序数组合并后的中位数
 * 设数组A和B，长度分别为m和n, 要求时间复杂度为O(log(m+n))。
 * 用二分查找的思想，求合并后数组的第k个数。每次二分的过程都要设法舍弃掉数组的一部分，从而达到收敛缩小查找范围的效果。
 * 从数组A和B分别取第k/2个数，当A[k/2-1] < B[k/2-1],则A的前k/2个元素必定在合并后的数组的前k个元素内，舍弃这A的前k/2个元素。
 * 否则，舍弃B中前k/2个数。
 * 接下来，递归在剩下的(m+n-k/2)的元素中找第(k-k/2)元素。
 * https://www.jiuzhang.com/qa/1768/
 */
public class MedianOfTwoSortedArrays {
    // 找到第K个元素
    private int findKth(int[] A, int iA, int jA, int[] B, int iB, int jB, int k) {
        int m = jA - iA + 1; // 数组A的长度
        int n = jB - iB + 1; // 数组B的长度
        if (n < m) return findKth(B, iB, jB, A, iA, jA, k); // 保证数组A长度比数组B长度小
        if (m == 0) return B[k - 1]; // 当较小的数组跑完了，返回数组B的第k个
        if (k == 1) return Math.min(A[iA], B[iB]); // 返回第1个数
        // 将k分成两部分
        int lenA = Math.min(k / 2, m); // 取数组A的前lenA个元素
        int lenB = k - lenA; // 取数组B的前lenB个元素
        int pa = iA + lenA - 1; // 数组A的第lenA个元素
        int pb = iB + lenB - 1; // 数组B的第lenB个元素
        // 判断A[pa]和B[pb]的大小
        if (A[pa] < B[pb]) return findKth(A, pa + 1, jA, B, iB, jB, k - lenA); // 舍弃数组A的前lenA个元素
        else if (A[pa] > B[pb]) return findKth(A, iA, jA, B, pb + 1, jB, k - lenB); // 舍弃数组B的lenB个元素
        else return A[pa]; // A[pa]或B[pb]就是对应的第k个数
    }

    public float getMedian(int[] A, int[] B) {
        int totalLen = A.length + B.length;
        if ((totalLen & 1) == 1) { // 总数组长度为奇数
            return findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2);
        } else { // 总数组长度为偶数
            return (findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2) +
                    findKth(A, 0, A.length - 1, B, 0, B.length - 1, totalLen / 2 + 1)) / 2.0f;
        }
    }