Question $3$

Consider the following recursive implementation of the Binary Search:

boolean binarySearch$($int arr$[],$ int left, int right, int key$)\{$

if $($right $$ left$)\{$

return false ;

$\}$

int mid $=$ left $+($right $-$ left$)/2$;

if $($arr$[$mid$]==$ key$)\{$

return true;

$\}$ else if $($arr$[$mid$]>$ key$)\{$

return binarySearch$($arr$,$ left, mid $-1,$ key$)$;

$\}$ else $\{$

return binarySearch$($arr$,$ mid $+1,$ right, key$)$;

$\}$

$\}$

Write the recurrence relation describing the time behavior of the routine above.

Use the recurrence relation to determine the growth function of the routine.