This program tests the function search(), which searches for an entry in an array. It illustrates subprograms, random access in arrays
The search.s program can be viewed as a text file by clicking here. After the file appears in a new tab or window it can be saved using your browser's file menu.
# This program tests the function search(), which searches for an
# entry in an array.
#
.globl main
.data
# Main program variables
#
# This is an example of a static array declaration with different
# values in each entry.
#
A: .word 1
.word 3
.word 5
.word 7
.word 9
.word 11
.word 13
.word 15
.word 17
.word 19
# Main program string constants
#
dataValueStr: .asciiz "Data value "
foundAtStr: .asciiz " found at index "
notFoundStr: .asciiz " not found"
endlineStr: .byte '.'
newlineStr: .asciiz "\n"
.text
# Main program.
#
# This program searches A for data values from 0 to 20 and displays the
# search results.
#
# Register usage:
#
# $s0 - data value to be found (variable data)
# $s1 - index where it is found (variable index)
# $s2 - constant 20
#
main:
li $s0, 0 # search for values from 0 to 20
li $s2, 20
b condTest
loop:
la $a0, A # index = search(A, 10, data)
li $a1, 10
move $a2, $s0
jal search
move $s1, $v0
li $v0, 4 # print "Data value "
la $a0, dataValueStr
syscall
li $v0, 1 # print data as decimal digit string
move $a0, $s0
syscall
beq $s1, -1, notFound # if index is -1 print not found
li $v0, 4 # else print " found at index "
la $a0, foundAtStr
syscall
li $v0, 1 # and print index as decimal digit string
move $a0, $s1
syscall
b endLine
notFound:
li $v0, 4 # print " not found"
la $a0, notFoundStr
syscall
endLine:
li $v0, 4 # print ".\n"
la $a0, endlineStr
syscall
add $s0, $s0, 1 # increment data
condTest:
ble $s0, $s2, loop # continue loop if data <= 20
li $v0, 4 # print "\n"
la $a0, newlineStr
syscall
li $v0, 10 # terminate the program
syscall
# function search
#
# C synopsis:
#
# int search(int A[], int numEntries, int searchVal)
#
# Typical C call:
#
# ind = search(A, numEntries, searchVal);
#
# Effect:
#
# Puts the index in A of the entry with value searchVal into ind.
# Puts -1 into ind if there is no such entry.
#
# Preconditions:
#
# The entries of A are in ascending numerical order.
#
# MAL call sequence:
#
# la $a0, A
# lw $a1, numEntries
# lw $a2, searchVal
# jal search
# sw $v0, ind
#
# Local variables:
#
# $t0 (lo) lowest possible index for searchVal
# $t1 (hi) highest possible index for searchVal
# $t2 (mid) index halfway between lo and hi
# $t3 (midAddr) address of A[mid]
# $t4 (midVal) A[mid]
#
search:
li $t0, 0 # lo = 0
sub $t1, $a1, 1 # hi = numEntries - 1
b searchLoopTest
searchLoop:
move $t2, $t0 # mid = (lo + hi)/2
add $t0, $t0, $t1
div $t0, $t0, 2
mul $t3, $t2, 4 # midAddr = mid*4 + address of A
add $t3, $t3, $a0
lw $t4, ($t3) # midVal = M[midAddr]
blt $a2, $t4, searchLower # if searchVal < midVal then
# search lower half of array segment
bgt $a2, $t4, searchHigher # if searchVal > midVal then
# search upper half of array segment
move $v0, $t2 # else found searchVal; return mid
jr $ra
searchLower:
sub $t1, $t2, 1 # try again with hi = mid - 1
b searchLoopTest
searchHigher:
add $t0, $t2, 1 # try again with lo = mid + 1
searchLoopTest:
ble $t0, $t1, searchLoop # continue loop if lo <= hi
li $v0, -1 # search failed; return -1
jr $ra