Descibe a recursive algorithm for finding the maximum elemen

Descibe a recursive algorithm for finding the maximum elements in an array, A, of n elements. What is your running time and space usage?

Explain how to modify the recursive binary search algorithm so that it returns the index of the target in the sequence or -1 (if the target is not found).

Solution

A. Finding maximum element in array:

function maximum( array [a1, a2, ...... an ] ):

if( length( array ) == 1 )

return a1;

int first = a1;

int maxInRestIs = maximum( array[a2, a3,.... an ] );

return max( first, maxInRestIs );

Running time is O(n) ,   Auxillary space usage is O(1) as recursive calls can be made by simply passing the pointer to second element of array when making the call

B.     For Binary search algorithm, when we find the target, we return A[mid] ( where \'mid\' is conventional name of variable used in Binary search algorithm ) , now instead we return mid itself. At last, after \'while\' loop finishes in the algorithm, we write \'return -1\' . If target is found, return mid statement is executed while it was in while loop . If not, -1 is returned.