Question $4.$ Exercise $2\mathrm{.}16$ from DPV$.$ You may get significant partial credit for a good verbal

explanation of your algorithm, but give clear, parseable pseudocode for full credit. Give an informal

but correct justification that your algorithm runs in logarithmic time.

$2\mathrm{.}16.$ You are given an infinite array $A[*]$ in which the first $n$ cells contain integers in sorted order and

the rest of the cells are filled with $.$ You are not given the value of $n.$ Describe an algorithm that

takes an integer $x$ as input and finds a position in the array containing $x,$ if such a position exists,

in $O(logn)$ time. $($If you are disturbed by the fact that the array A has infinite length, assume

instead that it is of length $n,$ but that you don't know this length, and that the implementation

of the array data type in your programming language returns the error message $$ whenever

elements $A[i]$ with $i>n$ are accessed.$)$