\problemdata                                                             
        {Binary Search Algorithm} % latex-friendly label for the prob.
        {Strong Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 2, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           

\textbf { Induction and Recursive Algorithms}

{\bf Procedure} $binary~search(x,i,j)$\\
$m:=\lfloor(i+j)/2\rfloor$\\
{\bf if} $x=a_m$ {\bf then}\\
$~~~~location:=m$\\
{\bf else if} ($x<a_m$ and $i<m$) {\bf then}\\
$~~~~binary~search$($x,i,m-1$)\\
{\bf else if} ($x>a_m$ and $j>m$) {\bf then}\\
$~~~~binary~search$($x,m+1,j$)\\
{\bf else } $location:=0$

The above procedure searches $x$ in a sequence $a_1,a_2,\ldots,a_n$
(when called with $i=1$, $j=n$).
Prove by (strong) induction that the binary search procedure 
sets $location$ to an index $i$ such that $a_i=x$, if there is such
an index, and otherwise sets $location$ to 0. 

\solution{
\medskip
\textbf{Solution:}\\
Proof by Strong Induction:\\

\textbf{P(n):} The binary search procedure correctly searches a list of length $
n$ such that the $location$ variable is set to $i$, where $a_i=x$, if such an in
dex exists, and otherwise $location$ is set to 0.\\

\textbf{Base Case:} P(1) - Calling binary search on an array consisting of one e
lement.  If that element is equal to $x$, then, according to the first \textit{i
f statement}, $location$ will be set equal to $\lfloor(i+2)/2\rfloor=\lfloor(1+1
)/2\rfloor=1$, as desired.  If, however, $a_1 \neq 1$, then since $i$ is not les
s than $m$ and $j$ is not greater than $m$ ($i=1, j=1, m=1$), the program would 
go to the final \textit{else statement}, where $location$ gets set to $0$, as de
sired.\\

\textbf{P(n+1):} To see that this procedure correctly searches a list
of length $(n+1)$, we need only to check that the two \textit{else if
statements} do the correct thing, because they each call binary search
on a smaller array, which, we know by our strong inductive hypothesis,
will get searched correctly.  Now, if the element we are looking for
($x$), is less than $a_m$ and $i<m$ (meaning that there are more
indices to search through), then the procedure gets called again on a
smaller array, that consisting of indices $i$ up to $m-1$.  We already
know the procedure searches this correctly by our strong inductive
hypothesis.  The second \textit{else if statement} does the same thing
if $x$ is bigger than our current element ($x>a_m$), and there is more
of the array to search through ($j>m$).  Therefore, the procedure
correctly calls itself on a smaller array, which by P(n) we know does
the correct search.  Therefore, we have show that $P(1)\vee P(2)\vee
P(3)\vee \ldots \vee P(n) \implies P(n+1)$, and our proof by strong
induction is complete.  }

\end{problem}                                  