# [leetcode] Median of Two Sorted Arrays

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

tag: divide and conquer, array, binary search

9/22/2015 update

Rewrite it in c++ version.

```class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if(len % 2 == 0){
return (findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2 - 1) + findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2)) / 2;
}
else{
return findKth(nums1, 0, nums1.size(), nums2, 0, nums2.size(), len / 2);
}
}
double findKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k){
if(end1 - start1 > end2 - start2){
//ensures nums1 is shorter than nums2
return findKth(nums2, start2, end2, nums1, start1, end1, k);
}
//base case
if(end1 - start1 == 0){
return nums2[start2 + k];
}
if(k == 0){
return min(nums1[start1], nums2[start2]);
}

int pa = min(k/2 + start1, end1 - 1);//nums1[pa] is always available
int pb = start2 + k - (pa - start1 + 1);//same to nums2
if(nums1[pa] == nums2[pb]){
//happy
return nums1[pa];
}
else if(nums1[pa] < nums2[pb]){
//median is in the right part of nums1 and left part of nums2
//nums1[pa] can't be the result but nums2[pb] can
//PREVIOUS BUG HRER
return findKth(nums1, pa + 1, end1, nums2, start2, pb + 1, k - (pa - start1 + 1));
}
else{
//median is in the left part of nums1 and right part of nums2
//nums2[pb] can not be the result but nums1[pa] can
//BUG HERE
return findKth(nums1, start1, pa + 1, nums2, pb + 1, end2, k - (pb - start2 + 1));
}
}
};```

1. 主函数中判断两个数组的长度和的奇偶性，根据中位数的定义来分清况调用递归函数。

2. 递归函数中，先保持m<n。然后将k平均分为两半pa,pb，在A和B中分别找第pa个数和第pb个数。如果两数相等，返回该值。

3. 如果A[pa – 1] > B[pb – 1]，则说明解在A的左半部分或B的右半部分，我们可以排除掉B的左半部分，所以k = k – pb

4. 如果A[pa – 1] < B[pb – 1]，则说明解在A的右半部分或B的左半部分，我们可以排除掉A的左半部分，所以k = k – pa

5. 注意处理递归到叶子节点时的情况，并要保持索引值小于M。

6. 时刻牢记，k指的是第k个值，而不是数组索引值(index)，在做运算时要考虑加一减一的问题。

```class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int length = m + n;
if (length & 0x1){//odd
return findKth(A, m, B, n, (length + 1) / 2);
}
else{//even
return (findKth(A, m, B, n, length / 2) +
findKth(A, m, B, n, length / 2 + 1)) / 2;
}
}
double findKth(int A[], int m, int B[], int n, int k){//k = 1,2,3...
if(m > n){//keep m < n
return findKth(B, n, A, m, k);
}
else if(m == 0){
return B[k - 1];
}
else if(k == 1){
return min(A[0], B[0]);
}
else{
int pa = min(k/2, m);
int pb = k - pa;
if(A[pa - 1] == B[pb - 1]){
return A[pa - 1];
}
else if(A[pa - 1] > B[pb - 1]){//result lies in the right part of B, the left part of A
return findKth(A, pa, B + pb, n - pb, k - pb);
}
else{//A[pa - 1] < B[pb - 1]
return findKth(A + pa, m - pa, B, pb, k - pa);
}

}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.