I need an algorithm that finds order statistics (K-th value) in combining 2 sorted lists in logarithmic time.
those. I have 2 sorted lists A[1..m]and B[1...n]. I need to find the K element in a sorted list that contains the values of 2 lists, and I need to do this at runtime O(lg(max(m,n)).
I know how to do this at runtime O(k), by scanning the minimalist values in both lists until I counted the elements of K.
but i don't know how to do it on O(lg(max(m,n)).
Any ideas?
Edit:
I see the solutions in a previous similar post , but the algorithm does not work there. for example, for lists: a = 13456, b = 278.
So maybe someone has another idea?
besad source
share