# 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 };``````