Thursday, June 13, 2013
Leetcode: Median of Two Sorted Arrays in C++
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)).
Either Drop the right side of Bigger one or left side of the small one.
Solution:
int findMid(int A[], int m, int B[], int n, int k)
{
if(m<=0) return B[k-1];
if(n<=0) return A[k-1];
if(k<=1)
return min(A[0], B[0]);
if(A[m/2]>B[n/2])
{
if(m/2+n/2+1<k)
return findMid(A, m, B+n/2+1, n - n/2-1, k-n/2-1 );
else
return findMid(A, m/2, B, n, k);
}
else
{
if(m/2+n/2+1<k)
return findMid(A+m/2+1, m- m/2-1, B, n, k-m/2-1 );
else
return findMid(A, m, B, n/2, k);
}
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if((m+n)%2==0)
return (findMid(A,m,B,n,(m+n)/2)+findMid(A,m,B,n,(m+n)/2+1))/2.0;
else
return findMid(A,m,B,n,(m+n)/2+1);
}
Labels:
Binary Search
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment