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

Question

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(log n) queries.

The idea is to use divide and conquer but I need some help thinking through this. Thanks!

Answer 1

I saw this problem on a qualifying exam not long ago, and it smells like a homework problem. I will therefore make only two suggestions:

• Study binary search, with careful attention to the precise nature of the loop invariants. Jon Bentley's book Programming Pearls has a good explanation

• Try generalizing the invariants for binary search.

• Draw a picture with various special cases:

  • Every number in DB1 is smaller than every number in DB2
  • Vice versa
  • DB1 equals DB2
  • Every number in DB2 is twice the corresponding number in DB1

This is a fairly hard problem; you'll have an easier time if you go straight for a proof of correctness.