# 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: 358

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