Question $4$

What is the asymptotic upper limit on the running time $($i$.$e$.$ the big$-$O$)$ of the following binary search:

def bs$($L$,$ item$)$:

if len$(L)==0$ :

return False

median $=$len$\frac{L}{\frac{?}{?}}2$

if item $==$ L$[$median$]$:

return True

elif item $$ L$[$median$]$:

return bs$($L$[$:median$],$ item$)$

else:

return bs$($L$[$median $+1$:$,$ item$)$

Show answer choices ${?}^{{?}^{?}}$

$($A$)O(n^2)$

$($B$)O(1)$

$($C$)O(n)$

$($D$)$ O$($logn$)$

$($E$)O(nlogn)$