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

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.