Ronzii's Blog

Just your average geek's blog

Find the k-th Smallest Element in the Union of Two Sorted Arrays

#include<iostream>
#include<climits>
using namespace std;
int findKthSmallest(int A[], int m, int B[], int n, int k)
{
    int i = (int)((double)m / (m+n) * (k-1));
    int j = k-i-1;
    int Ai_1 = (i==0)?INT_MIN:A[i-1];
    int Bj_1 = (j==0)?INT_MIN:B[j-1];
    int Ai = (i==m)?INT_MAX:A[i];
    int Bj = (j==n)?INT_MAX:B[j];
    if(Ai_1<Bj && Bj<Ai) return Bj;
    else if(Bj_1<Ai && Ai<Bj) return Ai;
    if(Ai<Bj) return findKthSmallest(A+i+1,m-i-1,B,n,k-i-1);
    else return findKthSmallest(A,m,B+j+1,n-j-1,k-j-1);
}
int main()
{
    int A[] = {7,9,12,14,15,18,34,71};
    int B[] = {5,9,10,13,15};
    int alength = sizeof(A)/sizeof(int);
    int blength = sizeof(B)/sizeof(int);
    cout<<findKthSmallest(A,alength,B,blength,8);
    return 0;
}
Advertisements

February 29, 2012 Posted by | C++ | , , , | Leave a comment

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;
}

July 26, 2011 Posted by | C++ | , , | Leave a comment