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);`

}

## 1 comment:

http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-in-union-of.html

## Post a Comment