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

Solution: 1. O(m+n)
2. O(log(m+n))
3. O(logm + logn)

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(int A[], int m, int B[], int n) {
 4         return findMedian(A, m, B, n, max(0, (m + n) / 2 - n), min(m - 1, (m + n) / 2));
 5     }
 6 
 7     double findMedian(int A[], int m, int B[], int n, int l, int r) {
 8         if (l > r)
 9             return findMedian(B, n, A, m, max(0, (m + n) / 2 - m), min(n, (m + n) / 2));
10 
11         int i = (l + r) / 2;
12         int j = (m + n) / 2 - i;
13 
14         int Ai_1 = (i == 0) ? INT_MIN : A[i-1];
15         int Bj_1 = (j == 0) ? INT_MIN : B[j-1];
16         int Ai = (i == m) ? INT_MAX : A[i];
17         int Bj = (j == n) ? INT_MAX : B[j];
18 
19         if (Ai < Bj_1) return findMedian(A, m, B, n, i+1, r);
20         if (Ai > Bj) return findMedian(A, m, B, n, l, i-1);
21 
22         if ((m + n) % 2 == 1) return Ai;
23         else return (Ai + max(Ai_1, Bj_1)) / 2.0;
24     }
25 };