在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)沒有（< =）

和對不起我的英語