https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。
示例 1:

nums1 = [1, 3]
nums2 = [2]
中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

思路

中位数，就是有序数组中间的数，如果对两个有序数组进行排序的话，那时间复杂度就是$O(m+n)$O(m+n)，不满足要求。所以找到中位数时，数组还是没有序的。
根据时间复杂度$O(log(m+n))$O(log(m+n))，能够想到二分查找，快速排序。快速排序的时间复杂度时$O(nlgn)$O(nlgn)，每一轮的时间复杂度是$O(n)$O(n)，一共$lgn$lgn轮；二分查找对一个有序的数组进行查找，比较当前位置，然后舍弃一半，每次时间复杂度为$O(1)$O(1)，进行了$lgn$lgn次。
$O(log(m+n))$O(log(m+n))判断一个位置是否是中位数，如果是则返回，如果不是，判断中位数在这个位置的那一边，这样就可以舍弃一半的数。时间复杂度就满足要求了。

如何判断

有序数组 nums1 和 nums2，长度分别为m和n，两个数组不同时为空。

假定nums1不为空，选定一个位置$p$p（$0 \le p &lt; n$0≤p<n）。假设nums1[p]是中位数，判断这个假设是否为真。

如果为真：
nums1[p]如果处于两个数组的中间位置的话，左右两边应该各有大概$(m+n)/2$(m+n)/2个数。
num1中比它小的数有多少个，比它大的数有多少个都是知道的。那么nums2中比它小，比它大的个数也就知道了。这样就可以在nums2中确定一个位置k。
然后检查nums2[k-1]<=nums1[p]<=nums2[k]是否成立。如果成立，那nums1[p]就是中位数。如果nums1[p]比两个值都小，说明，p右边的数比较多，那中位数在p的右边。否则，中位数在p的左边。

这个问题的难点是细节的处理，边界条件的判断。

java源码

package algorithm;

public class Median {

    private double result(int[] nums1, int[] nums2, int p, int k) {
        int m = nums1.length, n = nums2.length;
        if ((m+n)%2 == 1) return nums1[p];
        if ((p-1)>=0 && (k-1)>=0) {
            return (double)(Math.max(nums1[p-1], nums2[k-1])+nums1[p])/2;
        }
        if ((k-1)<0) return (double)(nums1[p]+nums1[p-1])/2;
        return (double)(nums1[p]+nums2[k-1])/2;
    }

    private double find(int[] nums1, int[] nums2, int s, int e) {

        int m = nums1.length, n = nums2.length;

        if (m == 0 || s>e) {
            return find(nums2, nums1, 0, n-1);
        }

        int p = (e-s+1)/2+s;
        int k = (m+n)/2-p;

        if (n == 0) {
            return result(nums1, nums2, p, k);
        }

        if (k < 0 || k > n) {
            int x = 0;
            if (k < 0) {
                x = p - (m + n - p - 1);
            } else {
                x = (p + n) - (m - p - 1);
            }

            if (x == 0 || x == 1) {
                return result(nums1, nums2, p, k);
            } else if (x < 0) {
                return find(nums1, nums2, p + 1, e);
            } else {
                return find(nums1, nums2, s, p - 1);
            }
        }

        if (k == 0) {
            if (nums1[p] <= nums2[k]) {
                return result(nums1, nums2, p, k);
            } else {
                return find(nums1, nums2, s, p-1);
            }
        }

        if (k == n) {
            if (nums1[p] >= nums2[k-1]) {
                return result(nums1, nums2, p, k);
            } else {
                return find(nums1, nums2, p+1, e);
            }
        }

        if (nums1[p] <= nums2[k] && nums1[p] >= nums2[k-1]) {
            return result(nums1, nums2, p, k);
        }

        if (nums1[p] > nums2[k]) {
            return find(nums1, nums2, s, p-1);
        }

        return find(nums1, nums2, p+1, e);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return find(nums1, nums2, 0, nums1.length-1);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{-1,3};

        Median median = new Median();
        double d = median.findMedianSortedArrays(nums1, nums2);
        System.out.print(d);
    }
}