Двоичный поиск с использованием рекурсии в сборке Mips

Question

У меня проблемы. Я пытался создать алгоритм двоичного поиска, используя рекурсию в сборке mips, но у меня есть некоторые ошибки, которые я не понимаю, как их решить.

У меня есть массив из 10 целых чисел, и я предполагаю, что массив отсортирован. это мой код, я признателен за любую помощь и заранее спасибо ..

  .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] 

это проблема, так как это не очень правильный индекс, как целое число занимает 4 байта поэтому средний вы получите от

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

только логический адрес не является реальным, что вам нужно будет умножить его с 4

mul $s4, $s1,4 

, а затем использовать $s4 в качестве адреса

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

также есть ошибка с условием остановки должно быть if (end < start) нет (< =)

и извините за мой английский