I need some algorithm that find the order statistic (the value of K-th) in the union of 2 sorted lists, on logarithmic time.
I.e. I have 2 sorted lists A[1..m] and B[1...n]. I need to find the item K in the sorted list which contain the values of the 2 lists, and I need to do that in run time- O(lg(max(m,n)).
I know how to do that in run time O(k), by scan the minimalist values in the both lists, until I counted K items.
but I don't know how to do that on O(lg(max(m,n)).
Any ideas?
Edit:
I see the solutions in previous similar post, but there aren't working algorithm there. for example for the lists: a=13456, b=278.
So, maybe someone has another idea?
