O(log n) algorithm to find the element having rank i in union of pre-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:23 UTC
Read the original article Hit count: 345

Filed under:

algorithm-design

|

c++

|

algorithm

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

Solutions for exercises in The Algorithm Design Manual

as seen on Stack Overflow - Search for 'Stack Overflow'
Does anybody know where to find solutions for the exercises in the book The Algorithm Design Manual? >>> More
Algorithm design, "randomising" timetable schedule in Python although open to other languages.

as seen on Stack Overflow - Search for 'Stack Overflow'
Before I start I should add I am a musician and not a native programmer, this was undertook to make my life easier. Here is the situation, at work I'm given a new csv file each which contains a list of sound files, their length, and the minimum total amount of time they must be played. I create… >>> More
Algorithm for dynamic combinations

as seen on Stack Overflow - Search for 'Stack Overflow'
My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to… >>> More
Disk Search / Sort Algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a Range of numbers say 1 to 10,000, Input is in random order. Constraint: At any point only 1000 numbers can be loaded to memory. Assumption: Assuming unique numbers. I propose the following efficient , "When-Required-sort Algorithm". We write the numbers into files which are designated… >>> More
Dynamic programming practice problems with solutions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is there a website or book that contains practice problems and solutions? Thanks Bala >>> More

Related posts about c++

Which C++ book shold I get between "C++ Primer" vs "C++ Primer Plus"

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to learn C++ by using Vim and MinGW as compiler. I'm interesting at "C++ Primer (4th Edition)" and "C++ Primer Plus (5th Edition)" but I don't know how about it different. It has no book store that I can review those books, so I want to know, what is the different between those book and which… >>> More
C++ : C++ Primer (Stanley Lipmann) or The C++ programming language (special edition)

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a Computer Science degree (long2 time ago) .. I do know Java OOP but i am now trying to pick up C++. I do have C and of course data structure using C or pascal. I have started reading Bjarne Stroustrup book (The C++ Programming Language - Special Edition) but find it extremely difficult esp… >>> More
I need help on my C++ assignment using MS Visual C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Ok, so I don't want you to do my homework for me, but I'm a little lost with this final assignment and need all the help I can get. Learning about programming is tough enough, but doing it online is next to impossible for me... Now, to get to the program, I am going to paste what I have so far. This… >>> More
Managed c++ std::string not accessible in unmanaged c++

as seen on Stack Overflow - Search for 'Stack Overflow'
In unmanaged c++ dll i have a function which takes constant std::string as argument Prototype : void read ( const std::string &imageSpec_ ) I call this function from managed c++ dll by passing a std::string. When i debug the unmanaged c++ code the parameter imageSpec_ shows the value correctly… >>> More
The Definitive C++ Book Guide and List

as seen on Stack Overflow - Search for 'Stack Overflow'
After more than a few questions about deciding on C++ books I thought we could make a better community wiki version. Providing QUALITY books and an approximate skill level. Maybe we can add a short blurb/description about each book that you have personally read / benefited from. Feel free to debate… >>> More