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

## AC代码

``````#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>

using namespace std;

double findKth(int A[], int m, int B[], int n, int k)
{
if(m > n)
return findKth(B,n,A,m,k);
if(m == 0)
return B[k - 1];
if(k <= 1)
return min(A[0], B[0]);

int pa = min(k / 2, m), pb = k - pa;
if(A[pa - 1] < B[pb - 1])
return findKth(A + pa, m - pa, B, n, k - pa);
else if(A[pa - 1] > B[pb - 1])
return findKth(A, m, B + pb, n - pb, k - pb);
else
return A[pa - 1];
}

double findMedianSortedArrays(int A[], int m, int B[], int n)
{
int k = m + n;
if(k & 0x1)
return findKth(A, m, B, n, k / 2 + 1);
else
return (findKth(A, m, B, n, k / 2) + findKth(A, m, B, n, k / 2 + 1)) / 2;
}

int main()
{
#ifndef ok
freopen("in4.in", "r", stdin);
freopen("std4.out", "w", stdout);
#endif

int m;
cin>>m;
int A[m];
for(int i = 0; i < m; i++)
cin>>A[i];
int n;
cin>>n;
int B[n];
for(int j = 0; j < n; j++)
cin>>B[j];
//	cout<<(float)findMedianSortedArrays(A, m, B, n)<<endl;

printf("%.5f\n", findMedianSortedArrays(A, m, B, n));
#ifndef ok
fclose(stdin);
fclose(stdout);
#endif

return 0;
}
``````