Ronzii's Blog

Just your average geek's blog

Median of 2 sorted arrays of equal lengths

#include <iostream>
using namespace std;
int median(int a[],int n)
{
    if(n%2==0)
    {
        return (a[n/2]+a[n/2-1])/2;
    }
    else
    {
        return a[n/2];
    }
}
int getMedian(int a[],int b[],int n)
{
    if(n==0)
    {
        return 0;
    }
    else if(n==1)
    {
        return (a[0]+b[0])/2;
    }
    else if(n==2)
    {
        return (max(a[0],b[0])+min(a[1],b[1]))/2;
    }
    int m1 = median(a,n);
    int m2 = median(b,n);
    if(m1==m2)
    {
        return m1;
    }
    else if(m1<m2)
    {
        return getMedian(a+n/2,b,n-n/2);
    }
    else
    {
        return getMedian(a,b+n/2,n-n/2);
    }
}
int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    cout<<getMedian(ar1, ar2, 5);
    return 0;
}
Advertisements

July 26, 2011 - Posted by | C++ | , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s