\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}
\newcommand{\twolists}{\mbox{{\sc 2Lists-Select}}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{9 February 1999}{13}

\begin{center}
\Large{\bf Solution to Bonus Problem of Problem Set 2}
\end{center}

\bigskip

{\bf 6. Selection from two sorted lists} (10 bonus points)

Design and analyze an efficient algorithm to select the median from a
set of $m+n$ keys given in the form of two sorted lists, one of length
$m$ and the other of length $n$.  For convenience, you may assume that
the $m+n$ keys are all distinct.  ({\em Hint:}\/ A running time of
$O(\log(\min\{m,n\}))$ is achievable.)

{\bf Answer:} We present an algorithm for selecting an element of arbitrary
rank $k$ from the two sorted lists.  The median can then be computed by
setting $k = \lfloor (m+n)/2 \rfloor$ or $k = \lceil (m + n)/2 \rceil$.  Let
the two sorted lists be $A[1..m]$ and $B[1..n]$.  Without loss of generality,
assume that $n \le m$.  The worst-case running time of our algorithm will turn
out to be $O(\log n)$.

The basic idea is to reduce the size of array $B$ by half in each iteration by
performing only a consant number of operations.  Thus, the number of
iterations will be $O(\log n)$ and so will the worst-case running time be.  In
the following pseudocode, $A$ and $B$ are the two given arrays, $p$ and $r$
are two indices of array $B$, $p \le r$, and $k$ is the rank that we are
seeking.  The algorithm returns the element of rank $k$ from the two sorted
lists $A$ and $B[p..r]$.  In order to find the median, we simply call $\twolists(A,
B, 1, n, \lfloor (m+n)/2 \rfloor)$.

\begin{tabbing}
$\twolists(A, B, p, r, k)$\\
\\
1. \= \myif\ \= $k < r - p + 1$ then \hs // No point in searching
$B[p+k..r]$\\
2. \> \> then $r = p + k - 1$\\
3. \> \myif\ $p = r$ then \hs // $B$ has only one element\\
4. \> \> \myif\ $A[k-1] > B[p]$ then \ret\ $A[k-1]$\\
5. \> \> \myelse\ \myif\ $A[k-1] < B[p]$ then \ret\ $\min\{A[k], B[p]\}$\\
6. \> \myelse\ \hs // $B$ has more than one element\\
7. \> \> $\ell = \lfloor (r - p + 1)/2 \rfloor$ \hs // $\ell$ is half the size of $B$\\
8. \> \> \myif\ $A[k - \ell] > B[p + \ell - 1]$ \hs // compare the middle element
of $B$ with appropriate element of $A$\\
9. \> \> then \ret\ $\twolists(A, B, p + \ell, r, k - \ell)$ \hs // discard first half of $B$\\
10. \> \> \myelse\ \ret\ $\twolists(A, B, p, p + \ell - 1, k)$ \hs // discard second half of $B$
\end{tabbing}

The worst-case running time of the algorithm is given by the recurrence $T(n)
= T(n/2) + \Theta(1)$, which yields $T(n) = \Theta(\log n)$ (like binary
search).
\end{document}

