O(log n) algorithm for computing rank of union of two sorted lists?

Posted by Eternal Learner on Stack Overflow See other posts from Stack Overflow or by Eternal Learner
Published on 2010-04-24T02:44:57Z Indexed on 2010/04/24 3:13 UTC
Read the original article Hit count: 397

Filed under:
|
|

Given two sorted lists, each containing n real numbers, is there a O(log?n) time algorithm to compute the element of rank i (where i coresponds to index in increasing order) in the union of the two lists, assuming the elements of the two lists are distinct?

I can think of using a Merge procedure to merge the 2 lists and then find the A[i] element in constant time. But the Merge would take O(n) time. How do we solve it in O(log n) time?

© Stack Overflow or respective owner

Related posts about algorithm-design

Related posts about c++