.data
A: .space 80 # integer array with 20 elements (A[20])
size_prompt: .asciiz "Enter a array size [between 1 and 20]: "
array_prompt: .asciiz "A["
sorted_array_prompt: .asciiz "A["
close_bracket: .asciiz "]"
close_bracket_equal: .asciiz "] = "
search_prompt: .asciiz "Enter search value: "
is_found: .asciiz " is found in "
not_found: .asciiz " not in array"
ensure_input: .asciiz "Ensure the input is sorted (Low to High)"
newline: .asciiz "\n"
.text
main:
la $s0, A # store address of array A in $s0
add $s1, $0, $0 # create variable "size" ($s1) and set to 0
add $s2, $0, $0 # create search variable "v" ($s2) and set to 0
add $t0, $0, $0 # create variable "i" ($t0) and set to 0
addi $v0, $0, 4 # system call (4) to print string
la $a0, size_prompt # put string memory address in register $a0
syscall # print string
addi $v0, $0, 5 # system call (5) to get integer from user and store in register $v0
syscall # get user input for variable "size"
add $s1, $0, $v0 # copy to register $s1, b/c we'll reuse $v0
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
addi $v0, $0, 4 # system call (4) to print string
la $a0, ensure_input # put string memory address in register $a0
syscall # print string
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
prompt_loop:
slt $t1, $t0, $s1 # if( i < size ) $t1 = 1 (true), else $t1 = 0 (false)
beq $t1, $0, end_prompt_loop
sll $t2, $t0, 2 # multiply i * 4 (4-byte word offset)
addi $v0, $0, 4 # print "A["
la $a0, array_prompt
syscall
addi $v0, $0, 1 # print value of i (in base-10)
add $a0, $0, $t0
syscall
addi $v0, $0, 4 # print "] = "
la $a0, close_bracket_equal
syscall
addi $v0, $0, 5 # get input from user and store in $v0
syscall
add $t3, $s0, $t2 # A[i] = address of A + ( i * 4 )
sw $v0, 0($t3) # A[i] = $v0
addi $t0, $t0, 1 # i = i + 1
j prompt_loop # jump to beginning of loop
end_prompt_loop:
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
addi $v0, $0, 4 # print "Enter search value: "
la $a0, search_prompt
syscall
addi $v0, $0, 5 # system call (5) to get integer from user and store in register $v0
syscall # get user input for variable "v"
add $s2, $0, $v0 # copy to register $s2, b/c we'll reuse $v0
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
binarySearch:
li $t1, 0 # left = 0
li $t2, 0 # middle = 0
subu $t3, $s1, 1 # right = size - 1
li $t4, -1 # elementindex = -1
whileLoop:
bgt $t1, $t3, end # end while when left > right
subu $t2, $t3, $t1 # Middle = right - left
srl $t2, $t2, 1 # Middle = (right - left) / 2
add $t2, $t2, $t1 # Middle = left + (right - left) / 2
sll $t6, $t2, 2 # index for A[Middle]
addu $s0, $0, $t6 # point to middle
lw $a0, 0($s0) # a0 = A[middle]
bne $a0, $s2, notEqual # if ( A[middle] == v) { IF NOT SKIP TO notEqual
add $t4, $0, $t2 # element_index = middle
j end # BREAK
notEqual:
slt $t5, $a0, $s2 # is A[middle] < v . IF YES, t5 = TRUE
beqz $t5, notLess
addi $t1, $t2, 1 # left = middle + 1
j pastnotLess
notLess:
subi $t3, $t2, 1 # right = middle - 1
pastnotLess:
j whileLoop
# END OF WHILE
end:
bge $t4, $0, notIndex
addi $v0, $0, 1 # system call (1) to print Int
la $a0, ($s2) # put string memory address in register $a0
syscall # search value
addi $v0, $0, 4 # system call (4) to print string
la $a0, not_found # put string memory address in register $a0 - printf( "%d not in sorted A\n", v );
syscall # not in sorted A
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
j exit
notIndex:
addi $v0, $0, 1 # system call (1) to print Int
la $a0, ($s2) # put string memory address in register $a0
syscall # Element
addi $v0, $0, 4 # system call (4) to print string
la $a0, is_found # put string memory address in register $a0
syscall # is found in
addi $v0, $0, 4 # system call (4) to print string
la $a0, sorted_array_prompt # put string memory address in register $a0
syscall #Sorted A[
addi $v0, $0, 1 # system call (1) to print Int
la $a0, ($t4) # put string memory address in register $a0
syscall # Element Index
addi $v0, $0, 4 # system call (4) to print string
la $a0, close_bracket # put string memory address in register $a0
syscall # ]
addi $v0, $0, 4 # system call (4) to print string
la $a0, newline # put string memory address in register $a0
syscall # NEWLINE
exit:
addi $v0, $0, 10 # system call (10) exits the progra
syscall # exit the program
