$1.$ Consider the following array:

A $=[10,3,4,2,7,14,8,6,9].$

$($i$)$ Let A$$ be the sorted array from part $($a$).$ Trace the binary search

algorithm for the keys k$1=12$ and k$2=4$ in A$$

$,$ separately. Determine the number of comparisons in each search.

$($ii$)$ Suppose a binary search tree T for n keys is given. What indicates

whether T is balanced?

$($iii$)$ Determine the efficiency class of the time complexity of the binary

search tree algorithm in the worst$-$case for each of the following

key sets K$1$ and K$2$ of each size n:

a$.$ The binary search tree constructed for K$1$ is balanced.

b$.$ The binary search tree constructed for K$2$ has height n $1.$