Question

Written in MIPS assembly language

If given an array which is sorted in ascending order, as well as its length and a target value. You are asked to find the index of this target value in the array using binary search algorithm. Here is an example: array 1, 4, 6, 8, 10, 12 length 6 target 8 2 In this case, the returned result should be assigned to be 3, as array[3] is equal to target. (Note: The target will exist in this array and will not be the first or last element, so there is no need to consider corner cases.) This task should be easy for high-level programming languages, such as C++, Java or Python. However, in this lab, you are asked to implement it in assembly language. Writing programs in a low-level language helps you learn how high-level operations are handled by CPUs.. The size of the sorted array can be fairly large, up to 2048 elements. Please avoid storing temporary variables in data memory (store them in registers instead). In order to simply your future work you the operators and operands that you are allowed to used in your code are limited to those given below: lui, lw, sw, add, sub, addi, srl, sll, and, or, andi, ori, xor, nor, slt, beq, bne, j, t0-t7, s0-s7, zero. Use the template "lab1-template.s" on git and fill the blank starting from "main:" with your code. (Please DO NOT change anything else.) SPIM automatically makes the program counter pc point to the main function when initialized. Your answer should be stored in the address of result, which is 0x10010008 in the template. Check you code with the provided correct pairs of input and output before submission.

Answer 1

# load $s0: base address
# load $s1: array size
# $s2: the search element
# return index at $v0 at address 0x10010008

.data
myArray:   .word 1, 4, 6, 8, 10, 12
arraySize: .word 6

.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]
    lw $t1,($t1)
    beq $t1, $s2, return       # if the arr[mid] is equal to search value, return mid
    slt $t2, $t1, $s2          # if mid < search, $t2 = 1
    beq $t2, $zero, leftHalf   # if mid > search, go left
    j   rightHalf              # if mid < 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