Question
CSE31: Project #2-Binary Search Overview You may choose to do this project by yourself or with a partner. The objective of this project is to practice the MIPS coding skills you have learned in the class. You will be implementing 2 algorithms in this project. Project Details All the source code is contained in BinarySearch.s. This program creates a list of integers based on user inputs. Then it performs Insertion Sort on the list. Finally it searches for a user defined key using Binary Search. Your task is to implement 3 of the functions described below. Make sure you DO NOT modify the main method! In order to understand how arguments are passed to the following functions, study the main function CAREFULLY printlist: It is a function to print out the content of a list. It takes in a list and its size as arguments. It does not return any value . inSort: It performs Insertion Sort in ascending order on a list. It takes in a list and its size as arguments. It returns the sorted list as a new list. You may use sorted list defined in the data segment in this function . bSearch: It performs a recursive Binary Search of a key on a list. It takes in a list, its size, and a search key as arguments. It returns 1 if the key exists in the list, otherwise it returns 0. You must implement this algorithm recursively therefore, be aware of the use of stack memory Create as many test cases as possible so that your program is free of error Sample output from BinarySearch.s: Test case #1: Enter size of list (between 1 and 25): 5 Enter one list element:
Explanation / Answer
.data original_list: .space 100 sorted_list: .space 100 str0: .asciiz "Enter size of list (between 1 and 25): " str1: .asciiz "Enter one list element: " str2: .asciiz "Content of original list: " str3: .asciiz "Enter a key to search for: " str4: .asciiz "Content of sorted list: " strYes: .asciiz "Key found!" strNo: .asciiz "Key not found!" .text #This is the main program. #It first asks user to enter the size of a list. #It then asks user to input the elements of the list, one at a time. #It then calls printList to print out content of the list. #It then calls inSort to perform insertion sort #It then asks user to enter a search key and calls bSearch on the sorted list. #It then prints out search result based on return value of bSearch main: addi $sp, $sp -8 sw $ra, 0($sp) li $v0, 4 la $a0, str0 syscall li $v0, 5 #read size of list from user syscall move $s0, $v0 move $t0, $0 la $s1, original_list loop_in: li $v0, 4 la $a0, str1 syscall sll $t1, $t0, 2 add $t1, $t1, $s1 li $v0, 5 #read elements from user syscall sw $v0, 0($t1) addi $t0, $t0, 1 bne $t0, $s0, loop_in move $a0, $s1 move $a1, $s0 jal inSort #Call inSort to perform insertion sort in original list sw $v0, 4($sp) li $v0, 4 la $a0, str2 syscall la $a0, original_list move $a1, $s0 jal printList #Print original list li $v0, 4 la $a0, str4 syscall lw $a0, 4($sp) jal printList #Print sorted list li $v0, 4 la $a0, str3 syscall li $v0, 5 #read search key from user syscall move $a3, $v0 lw $a0, 4($sp) jal bSearch #call bSearch to perform binary search beq $v0, $0, notFound li $v0, 4 la $a0, strYes syscall j end notFound: li $v0, 4 la $a0, strNo syscall end: lw $ra, 0($sp) addi $sp, $sp 8 li $v0, 10 syscall #printList takes in a list and its size as arguments. #It prints all the elements in one line. printList: #Your implementation of printList here move $t1, $a0 # A[0] li $s0, 0 # i = 0 forLoop: slt $t0, $s0, $a1 # checking i n exit the loop move $t3, $t2 # set another j = i nestedWhile: mul $t5, $t3, 4 # 4 * i add $t0, $t9, $t5 # assigning A[4 * i] ble $t3, 0, whileEnd # as long as #t3 > 0 while will run lw $t7, 0($t0) # $t7 = A[i] lw $t6, -4($t0)# $t6 = A[j-1] bge $t7, $t6, whileEnd # as long as arr[i]