Median of two Sorted Arrays

题目：

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

分析：

解法1实际是merge two sorted arrays。这么做下来，时间空间复杂度都是O(m + n); 注意返回值类型是double也就是说数组是偶数的时候，两个median求平均，但是这两个median是int啊，所以求平均的时候要转化为double。

然后面试官应该问你，能不能优化，优化就是O(log(m + n) )，想到了二分法。

解法2应该是二分法的第三重境界，就是每次除去一半的结果。解法2的函数接口需要传入(A, B, startA, startB, k)，其逻辑关系为：

1. 首先判断startA是否在A内能取到，若不能，则直接返回B的第k小元素
   同理也对B做判断。
2. 当k==1的时候返回A, B中第1小的元素
3. 再然后找到A的第k/2小元素和B的第k/2小元素。如果A的key小于B的key，则说明A的前k/2个元素不包含中位数，可以删除。
4. 在新的区间上递归，注意k - k/2和k/2不相等，在整形的情况下可能差1。

解法1：

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        // write your code here
        int sizeA = A.size();
        int sizeB = B.size();
        vector<int> merged(sizeA + sizeB);
        int i = 0;
        int j = 0;
        while (i < sizeA && j < sizeB) {
            if (A[i] < B[j]) {
                merged[i + j] = A[i];
                i++;
            } else {
                merged[i + j] = B[j];
                j++;
            }
        }
        while (i < sizeA) {
            merged[i + j] = A[i];
            i++;
        }
        while (j < sizeB) {
            merged[i + j] = B[j];
            j++;
        }
        int index = (sizeA + sizeB) / 2;
        if ((sizeA + sizeB) % 2 == 0) {
            return (merged[index] + merged[index - 1]) / 2.0;
        } else {
            return merged[index];
        }
    }
};

解法2

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findKthSmallest(vector<int> A, vector<int> B, int startA, int startB, int k) {
        if (startA >= A.size() ) {
            return B[startB + k - 1]; // index, so -1;
        }
        if (startB >= B.size() ) {
            return A[startA + k - 1];
        }
        if (k == 1) {
            return min(A[startA], B[startB]);
        }
        int medianA = (startA + k / 2 - 1 < A.size() ) ? A[startA + k / 2 - 1] : INT_MAX;
        int medianB = (startB + k / 2 - 1 < B.size() ) ? B[startB + k / 2 - 1] : INT_MAX;
        if (medianA < medianB) {
            return findKthSmallest(A, B, startA + k / 2, startB, k - k / 2);
        } else {
            return findKthSmallest(A, B, startA, startB + k / 2, k - k / 2);
        }
    } 

    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        // write your code here
        int sum = A.size() + B.size();
        if (sum % 2 == 1) {
            return findKthSmallest(A, B, 0, 0, sum / 2 + 1);
        } else {
            return (findKthSmallest(A, B, 0, 0, sum / 2) + findKthSmallest(A, B, 0, 0, sum / 2 + 1) ) / 2.0;
        }
    }
};