Question

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?

Answer 1

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!