The Program:
For this assignment, you will write a subroutine that performs a recursive binary search on an ordered array of 16 bit two's complement words. I have written all of the program for you except for the recursive binary search subroutine, which you must write.
This will copy the prog4.s file into the current working directory in your account. Since I have written much of the program for you, the files you should get are:
The program will prompt the user to enter an integer to search for. Output from the program will consist of either the logical position of the element in the array if found, or a "not found"
message if the element is not in the array.
binSearch.s Contains the recursive binary search subroutine, which you must write.

Subroutine Prototypes:
int getInput(char &buffer)
Reads input from the keyboard, validates that the input is a valid two's complement 16 bit integer, converts the input from ASCII to two's complement, and returns the converted integer. If the input entered is not valid, the V bit in the CCR is set, and the return value is undefined.
Load Point: $7000
int &binSearch(int key, int &low, int &hi)
Performs recursive binary search on the ordered array, and returns the address of the element in the array if it is found.
If the key is not in the array, then the subroutine sets the V bit in the CCR, and the return value is undefined.
Load Point: $8000

The "main" program (in prog4.s) does the following:
 Prints the title line.
 Prompts the user to enter an integer to search for.
 Calls getInput.
 Checks the CCR for valid input, and if V=1, then prints and error message and calls getInput until valid input is entered.
 Calls binSearch.
 If V=0, then the return value, which is the address of the found element, is used to determine the logical position of the element in the array, which is then printed.
 If V=1, then the program prints a "not found" message.

The datafile:
 Load Point: $6000
 The first word in the file is the number of elements in the array.
 following the count are the array elements, which are 16 bit two's complement integers.
ORG $6000
dc.w 10 *there are 10 elements in the array
dc.w 2,4,6,8,10,12,14,16,18,20
Note: The actual name of the data file is unimportant. Your program will be tested with a data file not available to you.

Sample Output:
Program #4, Main program by Alan Riggins
Enter the element to search for:
The element was found at position #6.
Program #4, Main program by Alan Riggins
Enter the element to search for:
The element was not found.

Recursive Binary Search Algorithm:
int &binSearch(int key, int &lo, int &hi) {
if(hi < lo)
return NOT_FOUND; //RETURN with V = 1
int mid = (lo+hi) / 2;
if(key == array[mid])
return mid;
else if(key < array[mid]) // go left
return binSearch(key, lo, mid-1); // left
return binSearch(key, mid+1, hi); // right

Additional Details:
 All code must obey structured programming principles.
 Registers may not be used to access parameters.
 All registers used in subroutines must be properly saved on the stack and restored on exit.
 The binSearch subroutine must be recursive.
 Subroutines may not use any storage allocation directives.
 Your program must load your binSearch subroutine at the addresses specified.
 Your program will be tested with an array not available to you.
 Your program must print the logical position of the array element if found. That is, if the element is located at array[0], then it is the first element in the array, and thus you will print
"The element is at position #1"
 Subroutines often use the CCR as a way to signal an error condition. When an error condition occurs, the V bit in the CCR is set to 1, and this serves as a flag to the calling program. This allows the programmer to do something that is impossible with many higher level languages--return two things from a function: the return value and the status. You can set the V bit
to 1 this way: move #2,CCR

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

    By purchasing this solution you'll be able to access the following files:

    for this solution

    or FREE if you
    register a new account!

    PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

    Find A Tutor

    View available Assembly Language Programming Tutors

    Get College Homework Help.

    Are you sure you don't want to upload any files?

    Fast tutor response requires as much info as possible.

    Upload a file
    Continue without uploading

    We couldn't find that subject.
    Please select the best match from the list below.

    We'll send you an email right away. If it's not in your inbox, check your spam folder.

    • 1
    • 2
    • 3
    Live Chats