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. The overall run time complexity should be O(log (m+n)).

tag: divide and conquer, array, binary search

9/22/2015 update

Rewrite it in c++ version.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();
        if(len % 2 == 0){
            return (findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2 - 1) + findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2)) / 2;
        }
        else{
            return findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2);
        }
    }
    double findKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k){
        if(end1 - start1 > end2 - start2){
            //ensures nums1 is shorter than nums2
            return findKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        //base case
        if(end1 - start1 == 0){
            return nums2[start2 + k];
        }
        if(k == 0){
            return min(nums1[start1], nums2[start2]);
        }
        
        int pa = min(k/2 + start1, end1 - 1);//nums1[pa] is always available
        int pb = start2 + k - (pa - start1 + 1);//same to nums2
        if(nums1[pa] == nums2[pb]){
            //happy
            return nums1[pa];
        }
        else if(nums1[pa] < nums2[pb]){
            //median is in the right part of nums1 and left part of nums2 
            //nums1[pa] can't be the result but nums2[pb] can
            //PREVIOUS BUG HRER
            return findKth(nums1, pa + 1, end1, nums2, start2, pb + 1, k - (pa - start1 + 1));
        }
        else{
            //median is in the left part of nums1 and right part of nums2
            //nums2[pb] can not be the result but nums1[pa] can
            //BUG HERE
            return findKth(nums1, start1, pa + 1, nums2, pb + 1, end2, k - (pb - start2 + 1));
        }
    }
};

挺难的题，我也是看了攻略才解出来。

这里阐述推广到在两个Sorted Arrays中找第k个数的算法。

1. 主函数中判断两个数组的长度和的奇偶性，根据中位数的定义来分清况调用递归函数。

2. 递归函数中，先保持m<n。然后将k平均分为两半pa,pb，在A和B中分别找第pa个数和第pb个数。如果两数相等，返回该值。

3. 如果A[pa – 1] > B[pb – 1]，则说明解在A的左半部分或B的右半部分，我们可以排除掉B的左半部分，所以k = k – pb

4. 如果A[pa – 1] < B[pb – 1]，则说明解在A的右半部分或B的左半部分，我们可以排除掉A的左半部分，所以k = k – pa

5. 注意处理递归到叶子节点时的情况，并要保持索引值小于M。

6. 时刻牢记，k指的是第k个值，而不是数组索引值(index)，在做运算时要考虑加一减一的问题。

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int length = m + n;
        if (length & 0x1){//odd
            return findKth(A, m, B, n, (length + 1) / 2);
        }
        else{//even
            return (findKth(A, m, B, n, length / 2) + 
                    findKth(A, m, B, n, length / 2 + 1)) / 2;
        }
    }
    double findKth(int A[], int m, int B[], int n, int k){//k = 1,2,3...
        if(m > n){//keep m < n
            return findKth(B, n, A, m, k);
        }
        else if(m == 0){
            return B[k - 1];
        }
        else if(k == 1){
            return min(A[0], B[0]);
        }
        else{
            int pa = min(k/2, m);
            int pb = k - pa;
            if(A[pa - 1] == B[pb - 1]){
                return A[pa - 1];
            }
            else if(A[pa - 1] > B[pb - 1]){//result lies in the right part of B, the left part of A
                return findKth(A, pa, B + pb, n - pb, k - pb);
            }
            else{//A[pa - 1] < B[pb - 1]
                return findKth(A + pa, m - pa, B, pb, k - pa);
            }
            
        }
    }
};