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$)$

There are $2$ base cases in this function $?$ and $?$

Group of answer choices

x is left of the pivot $|$ x i right of the pivot

array has $0$ elements $|$ array has $>1$ elements

array has $0$ elements $|$ middle element matches x

array has $1$ element $|$ array has $<$ n elements