Median of two sorted arrays

Median of two sorted arrays

Get the median

Get the median of two arrays, it's something like get the Kth element of two arrays. So we need to figure out the Kth problem

Some thing like binary search

We get k/2th element of array A, and k/2th element of array B. If they are equal, return k/2th element of array A. Otherwise, if ( A[k/2-1] > B[k/2-1] ), we need to find the k/2th element of array A and array B+k/2. After this, recursive.

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(int A[], int m, int B[], int n) {
 4         if ( (m+n)%2 == 1 ) {
 5             return findNth(A,m,B,n,(m+n)/2+1);
 6         } else {
 7             return double(findNth(A,m,B,n,(m+n)/2)+findNth(A,m,B,n,(m+n)/2+1))/2;
 8         }
 9     }
10     int findNth( int A[], int m, int B[], int n, int x ) {
11         if ( m == 0 ) {
12             return B[x-1];
13         }
14         if ( m > n ) {
15             return findNth(B,n,A,m,x);
16         }
17         if ( x == 1 ) {
18             return min(A[0],B[0]);
19         }
20         int m1 = min(m,x/2);
21         int m2 = x-m1;
22         if ( A[m1-1] == B[m2-1] ) {
23             return A[m1-1];
24         }
25         if ( A[m1-1] < B[m2-1] ) {
26             return findNth(A+m1,m-m1,B,n,m2);
27         }
28         return findNth(A,m,B+m2,n-m2,m1);
29     }
30 };
Loading Disqus comments...
Table of Contents