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
I hope this helps!