Binary search in MIPS assembly
<p>I am trying to write binary search algorithm in MIPS. Here's the problem:</p>

<blockquote>
  <p>Write a recursive procedure binarySearch that, given a sorted array A,
  an integer x, and indices left and right, searches for x in
  A[left..right]. If x exists in A[left..right], returns the location of
  x (index of x), otherwise returns −1 by putting the value in $v0. In
  your main, call the function and print out the result.</p>
</blockquote>

<p>Something going wrong in my code. All the comments shown in the code below:</p>

<pre><code># load $s0: base address
# load $s1: array size
# $s2: the search element
# return index at $v0

.data
myArray:   .word 1, 4, 5, 7, 9, 12, 15, 17, 20, 21, 30
arraySize: .word 11

.text

.globl main

main:
    # perform the first test
    addi $a1, $zero, 15
    jal  binarySearch
    add  $s3, $v0, $zero

exit:
    li $v0, 10
    syscall

binarySearch:
    la   $s0, myArray            # load the base address to $s0
    add  $a0, $zero, $zero       # $a0 is now the first index 0
    lw   $s1, arraySize          # load the array size to $s1
    addi $s1, $s1,  -1           # now $s1 is the last index
    add  $s2, $zero, $a1         # now store the search element into $s2

    j loop                       # do the loop

loop:
    add $t0, $s1, $a0          # have a temp reg to calculate the sum of  high and low
    sra $t1, $t0, 1            # store mid index value into $t1
    add $t1, $t1, $s0          # move to the arr[middle]
    beq $t1, $s2, return       # if the arr[mid] is equal to search value, return mid
    slt $t2, $t1, $s2          # if mid &lt; search, $t2 = 1
    beq $t2, $zero, leftHalf   # if mid &gt; search, go left
    j   rightHalf              # if mid &lt; search, go right

leftHalf:
    add $s1, $t1, -1             # modify the max, max=mid-1
    j do_loop                    # back to the loop

rightHalf:
    addi $t1, $t1,   1
    add  $a0, $zero, $t1         # modify the min, min=mid+1
    j    do_loop                 # back to the loop

return:
    add $ra, $zero, $t1
    jr  $ra
</code></pre>