## 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))`.

### 分析

`O(m+n)`的解法比较直观，直接merge两个数组，然后求第`k`大的元素。

* `A[k/2-1] == B[k/2-1]`
* `A[k/2-1] > B[k/2-1]`
* `A[k/2-1] < B[k/2-1]`

* 当A或B是空时，直接返回`B[k-1]`或`A[k-1]`；
* 当`k=1`是，返回`min(A[0], B[0])`；
* 当`A[k/2-1] == B[k/2-1]`时，返回`A[k/2-1]`或`B[k/2-1]`

### 代码

{% if book.java %}
{% codesnippet "./code/median-of-two-sorted-arrays."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% endif %}

{% if book.cpp %}
```cpp
// Median of Two Sorted Arrays
// Time Complexity: O(log(m+n))，Space Complexity: O(log(m+n))
class Solution {
public:
double findMedianSortedArrays(const vector& A, const vector& B) {
const int total = A.size() + B.size();
if (total %2 == 1)
return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
else
return (find_kth(A.begin(), m, B.begin(), n, total / 2)
+ find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
}
private:
static int find_kth(std::vector::const_iterator A, int m,
std::vector::const_iterator B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return *(B + k - 1);
if (k == 1) return min(*A, *B);

//divide k into two parts
int ia = min(k / 2, m), ib = k - ia;
if (*(A + ia - 1) < *(B + ib - 1))
return find_kth(A + ia, m - ia, B, n, k - ia);
else if (*(A + ia - 1) > *(B + ib - 1))
return find_kth(A, m, B + ib, n - ib, k - ib);
else
return A[ia - 1];
}
};
```
{% endif %}