Perform a box trace of the recursive function binarySearch, with the array 1, 5,

Question

Perform a box trace of the recursive function binarySearch, with the array
1, 5, 9, 12, 15, 21, 29, 31 for each of the following search values:

/** Searches the array anArray[first] through anArray[last]
for a given value by using a binary search.
@pre 0 <= first, last <= SIZE - 1, where SIZE is the
maximum size of the array, and anArray[first] <=
anArray[first + 1] <= ... <= anArray[last].
@post anArray is unchanged and either anArray[index] contains
the given value or index == -1.
@param anArray The array to search.
@param first The low index to start searching from.
@param last The high index to stop searching at.
@param target The search key.
@return Either index, such that anArray[index] == target, or -1.
*/
int binarySearch(const int anArray[], int first, int last, int target)
{
   int index;
   if (first > last)
       index = -1; // target not in original array
   else
   {
       // If target is in anArray,
       // anArray[first] <= target <= anArray[last]
       int mid = first + (last - first) / 2;
       if (target == anArray[mid])
           index = mid; // target found at anArray[mid]
       else if (target < anArray[mid])
           // Point X
           index = binarySearch(anArray, first, mid - 1, target);
       else
           // Point Y
           index = binarySearch(anArray, mid + 1, last, target);
   } // end if
   return index;
} // end binarySearch

a. 5
b. 13

Explanation / Answer

a. 5
Iteration1:
anArray = 1, 5, 9, 12, 15, 21, 29, 31
first = 0
last = 7
middle = 3
Now 5 is greater than anArray[0] and less than anArray[middle]

Iteration2:
anArray = 1, 5, 9, 12
first = 0
last = 4
middle = 9
Now 5 is greater than anArray[0] and less than anArray[middle]

Iteration3:
anArray = 1, 5, 9
first = 0
last = 2
middle = 1
Now 5 is equal to anArray[1], so return 1;

b 13
Iteration1:
anArray = 1, 5, 9, 12, 15, 21, 29, 31
first = 0
last = 7
middle = 3
Now 13 is greater than anArray[mid] and less than anArray[last]

Iteration2:
anArray = 12,15, 21, 29, 31
first = 3
last = 7
middle = 5
Now 13 is greater than anArray[mid] and less than anArray[last]

Iteration2:
anArray = 12,15, 21
first = 3
last = 5
middle = 4
Now 13 is greater than anArray[first] and less than anArray[mid]

Iteration2:
anArray = 12,15
first = 3
last = 4
middle = 0
return element not found

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.