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: 197
algorithm-design
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