This is a function which does a binary search, as we studied in class. We proved its correctness using induction. Answer the following regarding this function.

You may have additional questions on this exact code later in the exam.

pre: A is an array a$..$b of integers; a $<=$ b$+1$

function BinSearch $($A:Array, a$,$b: integer, x:eltype$)$

if a $>$ b then

return false

else

mid :$=($a$+$b$)$ div $2$

if x $=$ A$[$mid$]$ then

return true

else

if x $<$ A$[$mid$]$

return BinSearch$($A$,$ a$,$ mid$-1,$ x$)$

else

return BinSearch$($A$,$ mid$+1,$ b$,$ x$)$

The inductive hypothesis assumes that the algorithm is $\_?\_$

Group of answer choices

correct for problem sizes $>0$ and $<$ n

correct for $0$ elements

correct for any problem size n

incorrect if x $<>$ A$[$mid$]$