I have an assignment asking that from two sets M and N of equal size j holding distinct numbers, with access only to the functions kthsmallestM(int k) and kthsmallestN(int k), which return the k'th smallest integer from M and N respectively, the algorithm should find the j'th smallest element from M+N.
The way to do this using brute force is rather obvious, but the algorithm should run with O(log j) calls to kthsmallestM or kthsmallestN. I'm not looking for a complete solution, but I've been stuck on this for a while, so just some pointers to get me started would be appreciated!
What I've tried: Checking if the largest element of M is smaller than the smallest element of N and vice versa, in which case, the answer would simply be the largest element of M or N, depending on the situation. I tried using that to make a recursive algorithm that performs the same check for smaller elements of both sets, but that quickly turns into O(n).
Any tips?
The k smallest elements will include some number x of the smallest from M, and the k-x smallest from N.
If we make a guess about x, then we can use kthsmallestM(x), kthsmallestN(k-x), kthsmallestM(x+1) and kthsmallextN(k+1-x), to see whether our guess is too low, too high, or just right.
That means we can do a binary search to find the right value of x from 0 to j.