Find order statistics in a union of 2 sorted lists in logarithmic time

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?

+4
source share

Source: https://habr.com/ru/post/1537527/


All Articles