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