Exercise 1 Divide Search

Consider the algorithm binarySearch(A, p, r, x): the description of this algorithm is provided below.

Inputs:

• a sorted array A
• index p of the first element
• index r of last element
• an element x to search

Output:

• index of element x in Sequence A if x exists in A
• -1 if x does not exist in Sequence A.

Algorithm description

int binarySearch(A, p, r, x)

if (r >= p)

midpoint = p + (r-p)/2;

if A[midpoint] == x

return midpoint;

if A[midpoint] > x

return binarySearch(A, p, midpoint-1, x);

else

return binarySearch(A, midpoint+1, r, x);

return -1;

The objective of this exercise is to derive the time complexity (running) time of the divide search. (If interested, you could read about divide search on Wikipedia)

1. Let A = (-5, 7, 9, 15, 20, 30, 33, 37, 41, 55, 63, 65, 78, 102). Assume that the index of the first element is 1.
   1. Execute manually binarySearch(A,1, A.length, 65). What is the output?
   2. Execute manually binarySearch(A,1, A.length, 19). What is the output?
   3. Execute manually binarySearch(A,1, A.length, 102). What is the output?
   4. Execute manually binarySearch(A,1, A.length, -5). What is the output?
2. Which operation should you count to determine the running time T(n) of the divide search in a sequence A of length n?
3. Let us count the comparisons ((if A[midpoint] == x) and (if A[midpoint] > x)). Express the running time T(n) as a recurrence relation.
4. Solve the recurrence relation T(n) using the recursion-tree method
5. Solve the recurrence relation T(n) using the substitution method
6. Solve the recurrence relation T(n) using the master method