MIPS线性搜索结果异常及两种搜索比较次数统计求助

咱们一步步来解决你遇到的两个问题，先搞定线性搜索的错误，再处理比较次数的统计。

一、修复线性搜索的错误 #

问题根源 #

你调用binarySearch之后再调用linear，但binarySearch是递归函数，它会修改$a1和$a2这两个寄存器的值（递归过程中要更新左右边界）。当binarySearch返回时，$a2已经不是初始的数组长度10了，而是递归结束后的边界值。

举个例子：你查找目标2时，binarySearch最后会把$a2设为1，这时候linear的循环条件bge $s4, $a2会在s4=1时就跳出循环，根本没机会检查索引1对应的元素（也就是2），所以直接返回-1。

修复方案 #

有两种简单的修复方式，选哪种都可以：

方案1：调用linear前重新加载数组长度

在main函数里，调用binarySearch之后，重新从内存读取length到$a2，覆盖被修改后的值：

main:
la $a0, array
li $a1, 0
lw $a2, length
li $a3, 4  # 这里注释写错了，应该是"Load item to search for into $a3"
jal binarySearch
lw $a2, length  # 新增：重新加载数组长度
jal linear
# 后续打印代码不变

方案2：让linear自己读取数组长度

修改linear函数，直接从内存读取length，不依赖$a2参数，避免受前面函数的影响：

linear:
li $t0, 0  # 用$t0代替$s4，避免破坏调用者的$s寄存器（符合MIPS调用约定）
lw $t2, length  # 直接读取数组长度
j linearLoop
linearLoop:
bge $t0, $t2, linearFailed  # 用$t2代替$a2作为循环终止条件
lw $t1, 0($a0)
beq $t1, $a3, linearFound
addi $a0, $a0, 4
addi $t0, $t0, 1
j linearLoop
linearFound:
move $v1, $t0
j exitLoop
linearFailed:
li $v1, -1
j exitLoop
exitLoop:
jr $ra

这里额外提一句：MIPS的$s寄存器是被调用者保存的，也就是说如果你的函数（比如linear）要使用$s寄存器，需要先把它的值压栈保存，函数结束后恢复，否则会覆盖调用者（比如main）中$s寄存器的值。所以用$t寄存器代替$s4更稳妥。

二、统计两种搜索的比较次数 #

1. 线性搜索的比较次数统计 #

这个你思路是对的，每次循环都会做一次元素比较，我们只需要加一个计数器变量，每次比较时递增即可：

首先在.data段新增计数器变量：

.data
array: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
length: .word 10
newline: .asciiz " \n"
linear_count: .word 0  # 线性搜索比较次数计数器

然后修改linear函数，每次比较前（或后）更新计数器：

linear:
li $t0, 0
lw $t2, length
sw $zero, linear_count  # 每次搜索前重置计数器为0
j linearLoop
linearLoop:
bge $t0, $t2, linearFailed
lw $t1, 0($a0)
# 统计比较次数
lw $t3, linear_count
addi $t3, $t3, 1
sw $t3, linear_count
beq $t1, $a3, linearFound
addi $a0, $a0, 4
addi $t0, $t0, 1
j linearLoop

之后在main里打印计数器的值即可，比如在打印线性搜索结果后：

move $a0, $v1
li $v0,1
syscall
la $a0, newline
li $v0,4
syscall
# 打印线性搜索比较次数
lw $a0, linear_count
li $v0,1
syscall
la $a0, newline
li $v0,4
syscall

2. 二分搜索的比较次数统计 #

二分搜索是递归的，每次进入函数后都会做一次元素比较（beq和bgt是基于同一次加载的元素的判断，算一次比较），所以我们同样用全局计数器来统计：

首先在.data段新增计数器：

.data
# 其他变量...
binary_count: .word 0  # 二分搜索比较次数计数器

然后修改binarySearch函数，在加载数组元素后，更新计数器：

binarySearch:
addi $sp, $sp, -4
sw $ra, 0($sp)
blt $a2, $a1, binaryFailed

add $t0, $a1, $0
sub $t1, $a2, $a1
srl $t1, $t1, 1
add $t0, $t1, $t0
sll $t1, $t0, 2
add $t1, $t1, $a0
lw $t1, 0($t1)

# 统计比较次数
lw $t2, binary_count
addi $t2, $t2, 1
sw $t2, binary_count

beq $t1, $a3, binaryFound
bgt $t1, $a3, binaryGreater
addi $a1, $t0, 1
j binarySearch
j binaryEnd
# 后续binaryFound/binaryGreater/binaryFailed/binaryEnd代码不变

然后在main里调用binarySearch前重置计数器：

main:
la $a0, array
li $a1, 0
lw $a2, length
li $a3, 4
sw $zero, binary_count  # 重置二分搜索计数器
jal binarySearch
# 后续代码不变

最后在main里打印二分搜索的比较次数，比如在打印二分搜索结果后：

move $a0, $v0
li $v0, 1
syscall
la $a0, newline
li $v0,4
syscall
# 打印二分搜索比较次数
lw $a0, binary_count
li $v0,1
syscall
la $a0, newline
li $v0,4
syscall

这样就能准确统计两种搜索的比较次数了。

内容的提问来源于stack exchange，提问作者FloydVu0531