nth smallest number among two databases of size n each using divide and conquer

Posted by urfriend on Stack Overflow See other posts from Stack Overflow or by urfriend
Published on 2010-03-27T21:56:11Z Indexed on 2010/03/27 22:03 UTC
Read the original article Hit count: 306

we have two databases of size n containing numbers without repeats. So, in total we have 2n elements. They can be accessed through a query to one database at a time. The query is such that you give it a k and it returns kth smallest entry in that database. we need to find nth smallest entry among all the 2n elements in O(logn) queries. the idea is to use divide and conquer but i need some help thinking through this. thanks!

© Stack Overflow or respective owner

Related posts about divide-and-conquer

Related posts about algorithm