It looks like there are some errors in your code. For example, in the while loop, you are using the wrong register for the result. You should be using $t4 instead of $t6. Also, in the isGreater section, you are using the wrong register for the last pointer. You should be using $t1 instead of $t3. Additionally, you should be using the sw instruction to store the result in the result variable instead of the sw instruction in the exit section. Finally, you should be using the bne instruction instead of the beq instruction in the found section.
I hope this helps!
Hi there,
I need to implement in assembly mips an iterative binary search method.
Here's my code:
# this program implements binary search
# the equivalent pseudo code is the following:
# first = 0
# last = size -1
# while (last - first > 1) {
# mid = (last-first)/2 + first
# if A[mid] == val
# break;
# if A[mid] > val
# last = mid;
# continue
# else
# first = mid;
# continue;
# }
#-----------------------------------------------------
.data 0x10000000
size: .word 0x0000000a # array size
.data 0x10000004
search: .word 0x0000000d # search term
.data 0x10000008
result: .word 0xffffffff # result = -1
.data 0x10000100
array: .word 0x00000001 # the array
.word 0x00000005
.word 0x00000007
.word 0x00000009
.word 0x0000000b
.word 0x0000000d
.word 0x00000010
.word 0x00004000
.word 0x00050000
.word 0x00700000
.text 0x0400000
main:
sw $t0, 0 # $t0 = 0, that's our "first" pointer
sw $t1, size # $t1 - size
addi $t1, $t1, -1 # $t1 = size - 1, our "last" pointer
j condition # goto condition
nop
condition:
sub $t2, $t1, $t0 # $t2 = last - first
bgt $t2, 1, while # if ($t2 > 1) goto while
nop
j exit # if not, goto exit
nop
while:
div $t3, $t2, 2 # $t3 = (last - first) / 2
add $t3, $t3, $t0 # $t3 = t3 + first
lw $t5, array($t3) # $t5 = array($t3)
lw $t6, result # $t6 = result
beq $t6, $t5, found # if value found, goto found
nop
bgt $t5, $t6, isGreater # if array[$t3] > result, goto isGreater
nop
addi $t0, $t3, 0 # else, first = mid
j condition # check the condition and start over the loop
found:
sw $t3, result # result = $t3
j exit # goto exit
nop
isGreater:
addi $t1, $t3, 0 # else, last = mid
j condition # check the condition and start over the loop
exit: sw $t4, 4($t6) # result = $t4
j end # jump to end
nop
end: j end # internal loop to end the program
however when I try to run it I get errors of bad data.
Any ideas?
1 answer