Binary search
Twelve sorted words searched by halving the range four times, with the index left in t4 and -1 when the value is not there.
Twelve words in order, and the program finds which one holds 91 by halving the range it is looking in
until nothing is left. It leaves the index in t4, or -1 when the value is not in the array. Four
elements are read out of the twelve, where walking the array would read ten.
Bubble sort left an array in order. This is what being in order is worth: every comparison throws away half of what is left, so an array of a thousand elements takes about ten reads and one of a million takes about twenty.
You need to know: the "Arrays and strings" lecture and the "Bubble sort" Example. What is new here is a loop that jumps around its array instead of walking it, which is why the element is reached through an index rather than through a pointer that steps.
srli t5, t5, 1 is the halving: shifting a number one place right divides it by two and throws the
remainder away, which is the rounding down that (low + high) / 2 wants. srli is the shift that
brings zeroes in at the top, which is right here because an index is never negative; srai is the
one for a number that can be.
slli t6, t5, 2 turns the index into a byte offset, since the elements are words. That is the whole
of the difference between numbers[mid] in C and the two instructions here: C knows how big an
element is, and offset(base) adds one register to one constant and scales nothing.
bgt t2, t3, search_done is a pseudo-instruction and the assembler writes it as
blt t3, t2, search_done, the same encoding with its two registers the other way round. It borrows
no register to do that, so the three comparisons in this loop are three instructions and there is
nothing hidden in them.
addi t2, t5, 1 writes low from mid and adds one in the same instruction, which is what three
operands buy you: the M68K copies d4 into d1 and then increments it.
The four probes are 23, 72, 100 and finally 91. Each one either matches, or moves low past the
middle, or moves high below it, and the loop ends when low walks past high. t4 comes out at
00000009, which is the index of 91, and t2, t3 and t5 all end at 9 as well, which is the
range having closed onto one element. The whole search is 46 instructions.
Try changing li t1, 91 to li t1, 90, which is not in the array. t4 stays FFFFFFFF, the -1 the
li put there before the loop started, because a search that finds nothing has to say so and 0 is a
perfectly good index.