algorithm - MIPS,获取二分搜索和线性搜索的位置,
问题描述
我正在 MIPS 中编写一个程序,以使用线性搜索和二进制搜索从升序数组 (1-10) 中获取目标的位置。现在,我设法用正确的输出完成二进制算法,但是对于线性,数组中的一些整数导致输出不正确。
我现在的输出:
//Let's say the target to find = 2
1 //from binary search
-1 //from linear search, result -1 when can't find target
另一方面,我如何保持每个算法的比较次数?我知道线性情况是 O(n),基本上循环运行了多少次。但我不确定二进制搜索。
请帮我。
.data
array: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
length: .word 10
newline: .asciiz " \n"
.text
main:
la $a0, array # Load array into $a0
li $a1, 0 # Load 0 into a1
lw $a2, length # Load length into $a2
li $a3, 4 # Load item to search for into $a1
jal binarySearch
jal linear
move $a0, $v0 # Move $v0 into $a0
li $v0, 1 #print location of binary search
syscall #print
la $a0, newline
li $v0,4 #newline
syscall
move $a0, $v1
li $v0,1 #print location of target by linear search
syscall
la $a0, newline
li $v0,4 #new line
syscall
li $v0, 10
syscall
#length of the array: $a2
####################################
# Binary Search #
####################################
# Input: #
# $a0, the array of words #
# $a1, left index #
# $a2, right index #
# $a3, item to search for #
####################################
# Output: #
# $v0, index of item (-1 if failed)#
####################################
# Used Registers: #
# $t0, Midpoint #
# $t1, used in math #
####################################
binarySearch:
addi $sp, $sp, -4 # Lower stack pointer
sw $ra, 0($sp) # Store return address
blt $a2, $a1, binaryFailed # If r < l then we failed
# addi $t7, $t7, 1
add $t0, $a1, $0 # Move left into t0
sub $t1, $a2, $a1 # Right - Left
srl $t1, $t1, 1 # (Right - Left) / 2
add $t0, $t1, $t0 # left + (right - left) / 2 (MID)
sll $t1, $t0, 2 # Convert index into word format
add $t1, $t1, $a0 # Add offset into array
lw $t1, 0($t1) # Load array element into memory
beq $t1, $a3, binaryFound # The element was found
bgt $t1, $a3, binaryGreater # The element is greater than the pointer
addi $a1, $t0, 1 # Set left to mid+1
j binarySearch # Search with new variable
j binaryEnd
binaryFound:
add $v0, $t0, $0 # Move mid answer into memory
#move $s7, $t7
j binaryEnd # End
binaryGreater:
addi $a2, $t0, -1 # Set right to mid-1
jal binarySearch # Search with new right
j binaryEnd
binaryFailed:
li $v0, -1 # Load failed value
j binaryEnd # Load end
binaryEnd:
lw $ra, 0($sp) # Load the return
addi $sp, $sp, 4 # Raise stack poiner
jr $ra # Return
####################################
# End Binary Search #
####################################
###################################
#. Linear Search #
###################################
linear:
li $s4, 0 #index i = 0
j linearLoop
linearLoop:
bge $s4, $a2, linearFailed #if $t0 > target, it jumps out of loop
lw $t1, 0($a0) #load the array into t1
beq $t1, $a3, linearFound #if array[element] = target, found target
addi $a0, $a0, 4 #add 4 to the array size
addi $s4, $s4, 1 #add one to the index
j linearLoop #SOS THIS IS NO FUN !!!!!#
linearFound:
move $v1, $s4 #move $t0 into $v1
j exitLoop
linearFailed:
li $v1, -1
j exitLoop
exitLoop:
jr $ra
#############################
# END LINEAR SEARCH #
############################
解决方案
推荐阅读
- c++ - boost::asio 中的自定义处理程序
- perl - Perl 在警告时在正则表达式编译中使用未初始化的值
- html - 抓取 Github 提交作者元素
- javascript - 在 Node.js 和 MongoDB 上获取基于父数据的引用 ID
- google-maps - 如何检索物理地址的 Goo.gl/maps 链接
- c++ - 禁止孩子调用父母的抽象(或虚拟)函数
- javascript - 如何在不提供凭据的情况下在浏览器中使用 Kinesis Video Stream WebRTC SDK?
- c# - 如何从 CSV 文件流中删除标题
- typescript - 10秒间隔的查找速度
- linux - 如何在多字符字符串的 linux 中使用“cut”命令