Sarah Gerald 0 Newbie Poster

Hello all ,
I am having a problem in a homework which requires writing a recursive Binary search C code into MIPS

The question says that you have a 16 sorted integers
This is the C code

BinarySearch(A[0..N-1], key, low, high) {
if (high < low)
return -1 // not found
mid = (low + high) / 2
if (A[mid] > key)
return BinarySearch(A, key, low, mid-1)
else if (A[mid] < key)
return BinarySearch(A, key, mid+1, high)
return mid // found

and this is the code in mips I've written so far, but unfortunately it's not working


array: .word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Error: .asciiz "Not found"

li $v0,5 #input
addi $t0,$v0,0

li $s0,0
lw $a0,array($s0) # the first address of the array in $a0
la $a1,($t0)  #key
li $a2,0  #low
li $a3,15  #high
add $t0,$a2,$a3 #(low+high)
sra $s1,$t0,1 #$s1 is the mid now (low+high)/2
sll $s1,$s1,2 #we multiply the mid by 4 to use it as an offset 
lw $s3,array,($s1) #Array[mid]

jal binary_search


blt $a3,$a2,notfound #if(high<low)

bgt  $s3,$a1,larger #if(Array[mid]>key)

blt $s3,$a2,elseif #if(array[mid]<key)

j mid #else return mid 
li   $v0,4 #print a string 
la   $a0,Error

subi $s1,$s1,-1 #changing the value of mid to mid-1
add $a3,$0,$s1 #changing high to mid-1 
j binary_search

addi $s1,$0,1 #changing the value of mid to mid+1
add $a2,$0,$s1 #changing low to mid+1
j binary_search #make the recursion

li $v0,1 #print an integer
add $a0,$s2,$0 #print Mid 

any idea?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.