CS470

Programming assignment: Recursive binary search

In this MIPS programming assignment, you will write a program that will do a binary search.

Specifications:

• It must be done recursively, using a function that implements the function binary_search described by the psuedocode below.
• It must use the exact same stack frame as given in the green card.

The inputs and the output for the main program are:

Inputs:

• data is a array of word-sized unsigned integers sorted in ascending order,
• toFind is the integer to search for,
• count is the total number of elements in the array

Output:

• position of the integer toFind within array data,

-1 if not found

The array starts in location ARRY and the count is in location CNT. Assume that the minimum size of the array is three. The integer toFind should be input interactively, and the result should be printed.

Documentation: Use comments to document the program including the use of registers and the inputs/outputs of both functions.

Psuedocode for the subroutine

int binary_search(int *data, int toFind, int start, int end)

{

int mid = start + (end - start)/2; //Integer division

if (start > end)

return -1;

else if (data[mid] == toFind) //Found?

return mid;

else if (data[mid] > toFind) //search lower half

return binary_search(data, toFind, start, mid-1);

else //search upper half

return binary_search(data, toFind, mid+1, end);

}