Binäre Suche mit Rekursion in Mips-Assembly

Question

Ich habe ein Problem. Ich habe versucht, einen binären Suchalgorithmus mit Rekursion in Mips Assembly zu machen, aber ich habe einige Fehler, die ich nicht verstehe, wie man sie löst.

Ich habe ein Array von 10 ganzen Zahlen und ich nehme an, dass das Array sortiert ist. dies ist mein Code, ich schätze jede Hilfe und Dank im Voraus ..

  .data 
arr:  .word 40  
arrMsg: .asciiz "Enter the array : \n" 
posMsg: .asciiz "This value exist in the array and its position is " 
pos:  .word 0 
newline: .asciiz "\n" 
valMsg: .asciiz "Enter the value you search for : \n" 
val:  .word 0 
notfound:.asciiz "the value doesn't exist in the array !! \n" 
    .text 
main: 
    # print the array message 
    li $v0, 4 
    la $a0, arrMsg 
    syscall 

    # read the array from the user 
    # put $s0 = i 
    add $s0, $zero, $zero   # i = 0 
for: 
    beq $s0, 40, end 

    li $v0, 5 
    syscall 

    sw $v0, arr($s0)     # input arr[i] 
    addi $s0, $s0, 4     # i = i + 4 

    j for 
end:  

    # print value message 
    li $v0, 4 
    la $a0, valMsg 
    syscall 

    # read the value from the user 
    li $v0, 5 
    syscall 

    # store the value in the val variable 
    sw $v0, val 

    ################################################ 
    ## put $s0 = start , $s1 = middle , $s2 = end ## 
    ################################################ 
    li $s0, 0 
    li $s2, 9 

    jal BinarySearch 

    li $v0, 10 
    syscall 

    ############################################################################################################ 

BinarySearch: 

    # middle = (start + end)/2 
    add $t0, $s0, $s2     # $t0 = start + end 
    sra $s1, $t0, 1     # $s1 = $t0/2 

    # save $ra in the stack 
    addi $sp, $sp, -4 
    sw $ra, 0($sp) 

    # base case 
    ble $s2, $s0, returnNegative1  # if (end <= start) 

    lw $t1, arr($s1)     # $t1 = arr[middle] 
    lw $t2, val      # $t2 = val 
    beq $t1, $t2, returnMiddle   # if (arr[middle] == val) 

    blt $t2, $t1, returnFirstPart  # if (val < arr[middle]) 

    bgt $t2, $t1, returnLastPart  # if (val > arr[middle]) 

    returnNegative1: 
     li $v0, -1 
     j Exit  
    returnMiddle: 
     move $v0, $s1     # return middle 
     j Exit 

    returnFirstPart: 
      move $t3, $s1    # temp = middle  
      addi $t3, $t3, -1   # temp -- 
      move $s2, $t3    # end = temp 
      jal BinarySearch 
     j Exit 

    returnLastPart:        
     move $t3, $s1     # temp = middle 
     addi $t3, $t3, 1     # temp++ 
     move $s0, $t3     # start = temp 
     jal BinarySearch 
     j Exit 

Exit: 
    lw $ra, 0($sp) 
    addi $sp, $sp, 4` 
    jr $ra 

Answer 1

lw $t1, arr($s1)     # $t1 = arr[middle] 

dies das Problem ist, da es nicht wirklich der richtige Index als Integer 4 Byte nimmt so die mittlere Sie bekommen

add $t0, $s0, $s2     # $t0 = start + end 
sra $s1, $t0, 1     # $s1 = $t0/2 

ist nur die logische Adresse nicht die wirkliche Sie es mit 4

mul $s4, $s1,4 

multiplizieren müssen

und verwenden Sie dann $s4 als Adresse

lw $t1, arr($s4)     # $t1 = arr[middle] 

auch ein Fehler mit dem Stoppzustand ist sollte es sehr viel für mein Englisch