Find the k-th minimum in two sorted array

 

Question

      You have two sorted array of sizes m and n. How will find the k-th smallest number when these two sorted arrays are merged?

Try to get logarithmic performing algorithm

Answer

  I have not tried a logarithmic performing one. But a O(k) performance code is easy to do. Just take two indices in a merge algorithm and traverse it.

Code

int findKSmall(int* a, int m, int* b, int n, int k)

{

    int i=0;

    int j=0;

    int elem;

    while(k>0)

    {

        if(a[i] < b[j]) {

            if(i>m)

                continue;

            elem = a[i];

            i++;

        }

        else {

            if(j > n)

                continue;

            elem = b[j];

            j++;

        }

        k--;

    }

    return elem;

}

void main()

{

    int a[] = {2,4,6,9};

    int b[] = {8,10,14,21,32,44};

    int val = findKSmall(a,4,b,6, 10);

}