Median of two Sorted Arrays

    Example

    Given and B=[2,3,4,5], the median is 3.5.

    Given A=[1,2,3] and B=[4,5], the median is .

    Challenge

    The overall run time complexity should be O(log (m+n)).

    Java1 - merge sort with equal length

    Java2 - space optimization

    使用归并排序的思想做这道题不难，但是边界条件的处理比较闹心，使用归并排序带辅助空间的做法实现起来比较简单，代码也短。如果不使用额外空间并做一定优化的话需要多个 if 语句进行判断，需要注意的是多个 if 之间不能使用 else ，因为indexM1和indexM2有可能相等。

    复杂度分析

    时间复杂度 O(m + n), 空间复杂度为 (m + n)(使用额外数组), 或者 O(1)(不使用额外数组).

    题中已有信息两个数组均为有序，找中位数的关键在于找到第一半大的数，显然可以使用二分搜索优化。本题是找中位数，其实可以泛化为一般的找第 k 大数，这个辅助方法的实现非常有意义！在两个数组中找第k大数->找中位数即为找第k大数的一个特殊情况——第(A.length + B.length) / 2 大数。因此首先需要解决找第k大数的问题。这个联想确实有点牵强…

    1. 若k/2 - 1超出A的长度，则必取B[0]~B[k/2 - 1]

    C++

    源码分析

    本题用非递归的方法非常麻烦，递归的方法减少了很多边界的判断。此题的边界条件较多，不容易直接从代码看清思路。首先分析找k大的辅助程序。以 Java 的代码为例。

    1. 首先在主程序中排除 A, B 均为空的情况。
    2. 排除 A 或者 B 中有一个为空或者长度为0的情况。如果A_start > A.size() - 1，意味着A中无数提供，故仅能从B中取，所以只能是B从B_start开始的第k个数。下面的B…分析方法类似。
    3. k为1时，无需再递归调用，直接返回较小值。如果 k 为1不返回将导致后面的无限循环。
    4. 以A为例，取出自开始的第k / 2个数，若下标A_start + k / 2 - 1 < A.size()，则可取此下标对应的元素，否则置为int的最大值，便于后面进行比较，免去了诸多边界条件的判断。
    5. 比较A_key > B_key，取小的折半递归调用findKth。

    接下来分析findMedianSortedArrays：

    1. 首先考虑异常情况，A, B都为空。
    2. A+B 的长度为偶数时返回len / 2和 len / 2 + 1的均值，为奇数时则返回len / 2 + 1

    复杂度分析

    找中位数，K 为数组长度和的一半，故总的时间复杂度为 O(\log (m+n)).