O(log n) algorithm for merging lists and computing rank?

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 2:53 UTC
Read the original article Hit count: 196

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