mplementation by Binary Search $(18$p$,$ Question $1015)$ We shall implement

the previous specification by means of an algorithm FindB that maintains a search interval

B$[$lo$..$hi$]$ such that

if v belongs to B$[1..$n$]$ then v belongs to B$[$lo$..$hi$]$

and which narrows down that search interval $($by cutting in half; if say lo $=1$ and hi $=6$

then q becomes $3)$ until a suitable p has been found:

FindB$($v$,$ B$[1..$n$])$

lo$,$ hi $1,$n

found $$ false

while lo $<=$ hi and not found

q $($lo $+$ hi$)$ div $2$

if B$[$q$]=$ v

found $$ true

else if B$[$q$]>$ v

lo $??$L

else

hi $??$H

if found

return q

else

return $??$R

where you must provide suitables choices for

$10.(3$p$)??$L$$

$11.(3$p$)??$H$$

$12.(2$p$)??$R$.$

For the resulting algorithm,

$13.(2$p$)$ estimate $($as a function of n$)$ its worst$-$case running time

and simulate it $($by indicating how lo$,$ hi$,$ q and found change over time$)$ on the given example

$14.(4$p$)$ with v $=12$

$15.(4$p$)$ with v $=17.$