Q1. Consider the following function prototype and implementations of binary search on a vector of integers:

Prototype of binary search:

// This function performs a binary search in a vector v

// whose elements are in an ascending order.

// Vector v is searched for the value key.

// If key is found, the index of the position in v is

// returned. Otherwise, -1 is returned

Int binarySearch (const vector& v, int key);

Implementation of binary search:

Int binarySearch (const vector& v, int key)

{

Int first = 0; //index of the first element

Int last = v.size() -1; // index of the last element

Int middle; // index of the middle element

Int position = -1; // position of the value key

Bool found = false; // flag indicating whether the key was found

While (!found && first <=last)

{

middle = (first+ last) / 2; // integer division finds midpoint

if (v.at(middle) ==key)

{

found= true;

position=middle;

}

else if (v.at(middle)>key)

last = middle -1;

else

first = middle +1;

}

return position;

}

Write a recursive function binary search. Specify its prototype and its implementation.

-----------------------------------------------------------------------