How to find kth minimal element in the union of two sorted arrays?
- by Michael
This is a homework question. They say it takes O(logN + logM) where N and M are the arrays lengths.
Let's name the arrays a and b. Obviously we can ignore all a[i] and b[i] where i k.
First let's compare a[k/2] and b[k/2]. Let b[k/2] a[k/2]. Therefore we can discard also all b[i], where i k/2.
Now we have all a[i], where i < k and all b[i], where i < k/2 to find the answer.
What is the next step?