# Median of two Sorted Arrays

## Question

### Problem Statement

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

#### Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

#### Challenge

The overall run time complexity should be O(log (m+n)).

## 题解1 - 归并排序

### Java1 - merge sort with equal length

class Solution {
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
if ((A == null || A.length == 0) && (B == null || B.length == 0)) {
return -1.0;
}
int lenA = (A == null) ? 0 : A.length;
int lenB = (B == null) ? 0 : B.length;
int len = lenA + lenB;

/* merge sort */
int indexA = 0, indexB = 0, indexC = 0;
int[] C = new int[len];
// case1: both A and B have elements
while (indexA < lenA && indexB < lenB) {
if (A[indexA] < B[indexB]) {
C[indexC++] = A[indexA++];
} else {
C[indexC++] = B[indexB++];
}
}
// case2: only A has elements
while (indexA < lenA) {
C[indexC++] = A[indexA++];
}
// case3: only B has elements
while (indexB < lenB) {
C[indexC++] = B[indexB++];
}

// return median for even and odd cases
int indexM1 = (len - 1) / 2, indexM2 = len / 2;
if (len % 2 == 0) {
return (C[indexM1] + C[indexM2]) / 2.0;
} else {
return C[indexM2];
}
}
}


### Java2 - space optimization

class Solution {
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
if ((A == null || A.length == 0) && (B == null || B.length == 0)) {
return -1.0;
}
int lenA = (A == null) ? 0 : A.length;
int lenB = (B == null) ? 0 : B.length;
int len = lenA + lenB;
int indexM1 = (len - 1) / 2, indexM2 = len / 2;
int m1 = 0, m2 = 0;

/* merge sort */
int indexA = 0, indexB = 0, indexC = 0;
// case1: both A and B have elements
while (indexA < lenA && indexB < lenB) {
if (indexC > indexM2) {
break;
}
if (indexC == indexM1) {
m1 = Math.min(A[indexA], B[indexB]);
}
if (indexC == indexM2) {
m2 = Math.min(A[indexA], B[indexB]);
}
if (A[indexA] < B[indexB]) {
indexA++;
} else {
indexB++;
}
indexC++;
}
// case2: only A has elements
while (indexA < lenA) {
if (indexC > indexM2) {
break;
}
if (indexC == indexM1) {
m1 = A[indexA];
}
if (indexC == indexM2) {
m2 = A[indexA];
}
indexA++;
indexC++;
}
// case3: only B has elements
while (indexB < lenB) {
if (indexC > indexM2) {
break;
}
if (indexC == indexM1) {
m1 = B[indexB];
}
if (indexC == indexM2) {
m2 = B[indexB];
}
indexB++;
indexC++;
}

// return median for even and odd cases
if (len % 2 == 0) {
return (m1 + m2) / 2.0;
} else {
return m2;
}
}
}


## 题解2 - 二分搜索

1. A[k/2 - 1] <= B[k/2 - 1] => A和B合并后的第k大数中必包含A[0]~A[k/2 -1]，可使用归并的思想去理解。
2. 若k/2 - 1超出A的长度，则必取B[0]~B[k/2 - 1]

### C++

class Solution {
public:
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: a double whose format is *.5 or *.0
*/
double findMedianSortedArrays(vector<int> A, vector<int> B) {
if (A.empty() && B.empty()) {
return 0;
}

vector<int> NonEmpty;
if (A.empty()) {
NonEmpty = B;
}
if (B.empty()) {
NonEmpty = A;
}
if (!NonEmpty.empty()) {
vector<int>::size_type len_vec = NonEmpty.size();
return len_vec % 2 == 0 ?
(NonEmpty[len_vec / 2 - 1] + NonEmpty[len_vec / 2]) / 2.0 :
NonEmpty[len_vec / 2];
}

vector<int>::size_type len = A.size() + B.size();
if (len % 2 == 0) {
return ((findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0);
} else {
return findKth(A, 0, B, 0, len / 2 + 1);
}
}

private:
int findKth(vector<int> &A, vector<int>::size_type A_start, vector<int> &B, vector<int>::size_type B_start, int k) {
if (A_start > A.size() - 1) {
// all of the element of A are smaller than the kTh number
return B[B_start + k - 1];
}
if (B_start > B.size() - 1) {
// all of the element of B are smaller than the kTh number
return A[A_start + k - 1];
}

if (k == 1) {
return A[A_start] < B[B_start] ? A[A_start] : B[B_start];
}

int A_key = A_start + k / 2 - 1 < A.size() ?
A[A_start + k / 2 - 1] : INT_MAX;
int B_key = B_start + k / 2 - 1 < B.size() ?
B[B_start + k / 2 - 1] : INT_MAX;

if (A_key > B_key) {
return findKth(A, A_start, B, B_start + k / 2, k - k / 2);
} else {
return findKth(A, A_start + k / 2, B, B_start, k - k / 2);
}
}
};


### Java

class Solution {
/**
* @param A: An integer array.
* @param B: An integer array.
* @return: a double whose format is *.5 or *.0
*/
public double findMedianSortedArrays(int[] A, int[] B) {
if ((A == null || A.length == 0) && (B == null || B.length == 0)) {
return -1.0;
}
int lenA = (A == null) ? 0 : A.length;
int lenB = (B == null) ? 0 : B.length;
int len = lenA + lenB;

// return median for even and odd cases
if (len % 2 == 0) {
return (findKth(A, 0, B, 0, len/2) + findKth(A, 0, B, 0, len/2 + 1)) / 2.0;
} else {
return findKth(A, 0, B, 0, len/2 + 1);
}
}

private int findKth(int[] A, int indexA, int[] B, int indexB, int k) {

int lenA = (A == null) ? 0 : A.length;
if (indexA > lenA - 1) {
return B[indexB + k - 1];
}
int lenB = (B == null) ? 0 : B.length;
if (indexB > lenB - 1) {
return A[indexA + k - 1];
}

// avoid infilite loop if k == 1
if (k == 1) return Math.min(A[indexA], B[indexB]);

int keyA = Integer.MAX_VALUE, keyB = Integer.MAX_VALUE;
if (indexA + k/2 - 1 < lenA) keyA = A[indexA + k/2 - 1];
if (indexB + k/2 - 1 < lenB) keyB = B[indexB + k/2 - 1];

if (keyA > keyB) {
return findKth(A, indexA, B, indexB + k/2, k - k/2);
} else {
return findKth(A, indexA + k/2, B, indexB, k - k/2);
}
}
}


### 源码分析

1. 首先在主程序中排除 A, B 均为空的情况。
2. 排除 A 或者 B 中有一个为空或者长度为0的情况。如果A_start > A.size() - 1，意味着A中无数提供，故仅能从B中取，所以只能是B从B_start开始的第k个数。下面的B...分析方法类似。
3. k为1时，无需再递归调用，直接返回较小值。如果 k 为1不返回将导致后面的无限循环。
4. 以A为例，取出自A_start开始的第k / 2个数，若下标A_start + k / 2 - 1 < A.size()，则可取此下标对应的元素，否则置为int的最大值，便于后面进行比较，免去了诸多边界条件的判断。
5. 比较A_key > B_key，取小的折半递归调用findKth。

1. 首先考虑异常情况，A, B都为空。
2. A+B 的长度为偶数时返回len / 2和 len / 2 + 1的均值，为奇数时则返回len / 2 + 1