Median of Two Sorted Arrays

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)).




------------------------------ codes --------------------------------------
//using recursive method to solve the problem

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m+n)%2 == 1) {
            return findKthSortedArray(A, 0, m-1, B, 0, n-1, (m+n)/2 + 1);
        } else {
            int a1 = findKthSortedArray(A, 0, m-1, B, 0, n-1, (m+n)/2);
            int a2 = findKthSortedArray(A, 0, m-1, B, 0, n-1, (m+n)/2 + 1);
            return (double)(a1+a2)/2.0;
        }
    }
    int findKthSortedArray(int A[], int start1, int end1, int B[], int start2, int end2, int k) {
        if (k == 1) {
            int a1 = (start1 <= end1?A[start1]:INT_MAX);
            int a2 = (start2 <= end2?B[start2]:INT_MAX);
            return a1<a2?a1:a2;
        }
        int mid = k / 2;
        //bug here -> the index of a1 and a2 should be start1 + mid - 1 & start2 + k - mid - 1
        int a1 = (start1 + mid - 1) <= end1 ? A[start1 + mid - 1]:INT_MAX;
        int a2 = (start2 + k - mid - 1) <= end2 ? B[start2 + k - mid - 1]:INT_MAX;
        if (a1 < a2) {
            return findKthSortedArray(A, start1 + mid, end1, B, start2, end2, k - mid);
        } else {
            return findKthSortedArray(A, start1, end1, B, start2 + k - mid, end2, mid);
        }
    }
};