Using MIPS in QTSPIM, Write a subroutine that performs a binary search on the data entered by the user.

Run these 4 experiments on your code. The experiment details are:

Input 8 integers. Do not enter them in order, they should be put in order by the stack-control routine from

1.search for the smallest integer that you had entered

2.search for the largest integer that you had entered

3.search for an integer near the median of the list entered

4.search for an integer that doesnt exist

Note: These searches can be done in separate runs, you do not have to write code to run all four tests in a single run.

?Your main routine must read from input the value to be searched and pass value to the search subroutine using an $a register. Of course this will happen after inputting the 8 ints.

?The search subroutine should return 0 if the integer was not found and 1 if it was This

value must be returned on $v0 register.

?The main method only needs to report whether or not the integer was found based on

the return value of the subroutine.

?Remember, your ?search subroutine will need to store data on the stack before it calls itself recursively

Pseudo code for binary Search:

# val is the int to be searched

# low is the lowest index of the portion of the array (stack) to be searched

# high is the highest index of the portion of the array to be searched

int binSearchRec(int val, uint &s, int low, int high) {

if (low > high)

return 0;

int mid = (low + high) / 2;

if (s[mid] == val)

return 1;

else if (s[mid] < val)

return binSearchRec(val, s, mid + 1, high);

Else

return binSearchRec(val, s, low, mid - 1);

}

So far I have this code. It needs modifications and some fixes to fit the prompt above.

///////////////////////////////

.data

n: .asciiz "Quantity of ints to store:"

val: .asciiz "Enter integer:"

result: .asciiz " Your sorted ints:"

space: .asciiz " "

#Main method

.text

.globl main

main:

#int i=0;

add $a1,$0,$0

#prompt user to enter quantity of integers going to enter

la $a0,n

li $v0,4

syscall

#Read quantity

li $v0,5

syscall

#store n in a0

move $a0,$v0

#store n in s0 for reuse

move $s0,$v0

#move n to $t0

move $t0,$a0

move $t1, $a0 #for sortarray

#call stacking function

jal priorityArray

#int i=0;

add $a1,$0,$0

#result prompt

la $a0,result

li $v0,4

syscall

#print values loop

priorityQ:

#i

bge $a1,$s0,exit

#prompt for integer entry

la $a0,space

li $v0,4

syscall

#take from stack

lw $a0,4($sp)

#print value

li $v0,1

syscall

#i++

addi $a1,$a1,1

#decrement stack to store value

addi $sp,$sp,4

#loop continue

j priorityQ

priorityArray:

#i<

bge $a1,$t0,return

#prompt for integer entry

la $a0,val

li $v0,4

syscall

#Read integer

li $v0,5

syscall

#store in stack

sw $v0,0($sp)

#i++

addi $a1,$a1,1

#decrement stack to store value

addi $sp,$sp,-4

#loop continue

j priorityArray

return:

#return function

jr $ra

exit:

#exit from the program

li $v0,10

syscall