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