CSC $204-$ Algorithm Design and Analysis

Homework $2-$ Divide and Conquer and Solving Recurrences

Name:

Student

Binary Search $($recursive$)(20$ points$)$

Binary Search is an algorithm that takes as input a sorted array $A,$ a specific value to search

for, $x,$ and the start index and end index of the subarray to search in$.$ It begins by checking the

middle of the entire array A $.$ If the middle of the array contains the value being searched for

then the function returns the index. If the value in the middle of the array is not equal to the

value being searched for, then this process is repeated on either the left or the right subarray. If

the value $x$ is not found in the array, then the function should return $-1.$ In Homework #$1$ the

pseudocode for the iterative version of Binary$-$Search was given. Now we will explore the

recursive version

$($a$)$ Write pseudocode for the recursive function Binary$-$Search. You may NOT change the

function signature. $(10$ points$)$

Binary$-$Search$($A$,x,$ start$\_$index, end$\_$index$)$

$($b$)$ Write down the recurrence equation for the worst$-$case running time of Binary$-$Search. $(2$

points$)$

$T(n)=$

$($c$)$ Draw the recursion tree for the recurrence equation of the worst case of Binary$-$Search.

Include at least $3$ levels. $(2$ points$)$

$($d$)$ For an input of size $n,$ how many levels are there in the recursion tree for the worse case?

$(2$ points$)$

$($e$)$ Based on your recursion tree, give an asymptotic tight bound for the worst case running

time of Binary$-$Search. $(2$ points$)$

$T(n)=(,)$

$($f$)$ Based on the master theorem for solving recurrences, show how you end up with the same

running time as in part $($e$).$ State the values for $a,b,$ and $f(n),$ and show which case of the

master theorem you are using. $(2$ points$)$

$a=$

Master Theorem Case $\frac{?}{?}$#:

$b=$

$f(n)=$