SKETCH: Assuming that you’re allowed to use extra storage, run the comparison as a single elimination tournament, keeping a record of the entries beaten by each winner along the way. (Low number wins.) When you get an overall winner, you have only to identify the winner among the $\lceil \lg n\rceil$ contestants beaten by the overall winner.
Added: On further thought, I see that one doesn’t actually need additional memory, if one rearranges the list. Implement the single elimination tournament as follows.
Suppose that the numbers are $a_0,a_1,\dots,a_{n-1}$. On the first pass compare $a_{2k}$ with $a_{2k+1}$ for $0\le k<(n-1)/2$; if $a_{2k}>a_{2k+1}$, interchange them. On the second pass compare $a_{4k}$ with $a_{4k+2}$ for $0\le k<(n-2)/4$; if $a_{4k}>a_{4k+2}$, interchange the pair $\langle a_{4k},a_{4k+1}\rangle$ with the pair $\langle a_{4k+2},a_{4k+3}\rangle$. On the $i$-th pass compare $a_{2^ik}$ with $a_{2^ik+2^{i-1}}$ for $0\le i<(n-2^{i-1})/2^i$; if $a_{2^ik}>a_{2^ik+2^{i-1}}$, interchange the blocks of length $2^{i-1}$ beginning at $a_{2^ik}$ and $a_{2^ik+2^{i-1}}$. This continues as long as $n-2^{i-1}>0$, i.e., until $n\le 2^{i-1}$; thus, if the last pass is the $m$-th pass, then $2^{m-1}<n\le 2^m$, or $\lceil\lg n\rceil=m$. The smallest number in the set is now $a_0$, and every other number in the set has lost exactly one comparison, so we’ve made $n-1$ comparisons.
The numbers that are now $a_{2^i}$ for $i=0,\dots,m-1$ are the numbers that lost to $a_0$ in direct comparisons; every number in the set that is neither $a_0$ nor one of these $m$ numbers lost a direct comparison to one of these $m$ numbers and therefore cannot be the second-smallest number in the set. Thus, the second-smallest number is the smallest of the $a_{2^i}$ for $i=0,\dots,m-1$. There are $m$ of these numbers, so it takes $m-1$ comparisons to find the smallest.
Altogether, then, this algorithm takes $$(n-1)+(m-1)=n-1+\lceil\lg n\rceil-1=n+\lceil\lg n\rceil-2$$ comparisons, as required.
Best Answer
Hint: What you want is to find $p$ such that $X[\frac n2 + p]=Y[\frac m2 -p]$. In the spirit of bisection, start with $p=0$. If $X[\frac n2] \gt Y[\frac m2]$ you need to decrease $p$, while if $X[\frac n2] \lt Y[\frac m2]$ you need to increase $p$.