How to find the kth smallest element in the union of two sorted arrays?
algorithm, arrays, binary-search, divide-and-conquer
Solution
You've got it, just keep going! And be careful with the indexes...
To simplify a bit I'll assume that N and M are > k, so the complexity here is O(log k), which is O(log N + log M).
Pseudo-code:
i = k/2
j = k - i
step = k/4
while step > 0
if a[i-1] > b[j-1]
i -= step
j += step
else
i += step
j -= step
step /= 2
if a[i-1] > b[j-1]
return a[i-1]
else
return b[j-1]
For the demonstration you can use the loop invariant i + j = k, but I won't do all your homework :)
Problem
This is a homework question, binary search has already been introduced: Given two arrays, respectively N and M elements in ascending order, not necessarily unique: What is a time efficient algorithm to find the kth smallest element in the union of both arrays? 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?