水中的鱼: [LeetCode] 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)).

1:    double findMedianSortedArrays(int A[], int m, int B[], int n) {  
2:      if((n+m)%2 ==0)  
3:      {  
4:        return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;  
5:      }  
6:      else  
7:        return GetMedian(A,m,B,n, (m+n)/2+1);        
8:    }  
9:       int GetMedian(int a[], int n, int b[], int m, int k)  
10:       {  
11:            assert(a && b);   
12:            if (n <= 0) return b[k-1];  
13:            if (m <= 0) return a[k-1];  
14:            if (k <= 1) return min(a[0], b[0]);   
15:            if (b[m/2] >= a[n/2])  
16:            {  
17:                 if ((n/2 + 1 + m/2) >= k)  
18:                      return GetMedian(a, n, b, m/2, k);  
19:                 else  
20:                      return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1));  
21:            }  
22:            else  
23:            {  
24:                 if ((m/2 + 1 + n/2) >= k)  
25:                      return GetMedian( a, n/2,b, m, k);  
26:                 else  
27:                      return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));  
28:            }  
29:       }  

Read full article from 水中的鱼: [LeetCode] Median of Two Sorted Arrays 解题报告