Recherche dichotomique MIPS

	.data
tab:
	.word	1
	.word	7
	.word	19
	.word	223
	.word	511
	.word	517
	.word	603
	.word	1020
	.word	1011
	.word	1022

	.text
main:
	la $a0, tab          # chargement de l'adresse de la première cellule du tableau dans $a0
	li $a1, 0            # chargement de l'index du premier element du tablau (0 of course) dans $a1
	li $a2, 9            # chargement de l'index du dernier element du tableau taille du talbeau -1 == 9 dans $a2
	li $a3, 603          # chargement de la valeur recherchee dans $a3 ici $a3 = 603

	addi $sp, $sp, -4
	sw $ra, 0($sp)

	jal recherche        # appel de recherche

	lw $ra, 0($sp)
	addiu $sp, $sp, 4
	jr $ra

recherche:
	bgt $a1, $a2, error   # si $a1 > $a2, la recherche est impossible donc on branche a error:

	sub $t0, $a2, $a1     # $t0 = $a1+($a2-$a1)/2
	srl $t0, $t0, 1       # decalage de 1 bit vers la droite (divise par 2)
	add $t0, $t0, $a1     # $t0 contient maintenant l'index du milieu du tableau

	addiu $sp, $sp, -8    # on deplace le pointeur de pile de 8

	sw $ra, 0($sp)        # on sauve l'adresse de retour avec un offset de 0
	sw $t0, 4($sp)        # on sauve l'index du milieu du tableau avec un offset de 4

	sll $t0, $t0, 2       # decalage de 2 bits vers la gauche (multiplie par 4)
	add $t0, $t0, $a0     # addition de $t0 avec l'adresse du début du tableau

	lw $t1, 0($t0)        # on charge la valeur qui est stockee à l'adresse $t0 du tableau

	beq $a3, $t1, found   # cas ou la valeur contenue dans $t1 est egale a la valeur recherchee (contenue dans $a3)
	                      # branchement à found:

	blt $a3, $t1, rec1    # cas ou la valeur contenue dans $t1 est plus grand que la valeur recherchee (contenue dans $a3)
	                      # branchement à rec1:

	bgt $a3, $t1, rec2    # cas ou la valeur contenue dans $t1 est plus petite que la valeur recherchee (contenue dans $a3)
	                      # branchement à rec2:

                          # cas ou $a1 > $a2
error:
	li $v0, -1            # chargement de la valeur -1 dans le registre de retour de fonction $v0 ce qui indique que l'element
	                      # n'a pas été trouvé
	jr $ra

                          # cas ou la valeur contenue dans $t1 est egale a la valeur recherchee (contenue dans $a3)
found:
	lw $v0, 4($sp)        # chargement de la valeur de l'index dans le registre $v0
	lw $ra, 0($sp)        # chargement de l'adresse de retour dans le registre $ra
	addiu $sp, $sp, 8     # on remet le pointeur de pile à sa position d'origine
	jr $ra

                          # cas ou la valeur contenue dans $t1 est plus grand que la valeur recherchee
rec1:
	lw $a2, 4($sp)        # chargement de l'index de moitie du tableau dans le registre $a2 qui est le parametre du haut du
	                      # tableau
	addiu $a2, $a2, -1    # paramétrage du registre $a2 pour l'appel recursif

	jal recherche         # appel recursif

	lw $ra, 0($sp)        # chargement de l'adresse de retour dans le registre $ra
	addiu $sp, $sp, 8     # on remet le pointeur de pile à sa position d'origine
	jr $ra

	                      # cas ou la valeur contenue dans $t1 est plus petite que la valeur recherchee
rec2:
	lw $a1, 4($sp)        # chargement de l'index de moitie du tableau dans le registre $a1 qui est le parametre du haut du
	                      # tableau
	addiu $a2, $a2, 1     # paramétrage du registre $a2 pour l'appel recursif

	jal recherche         # appel recursif

	lw $ra, 0($sp)        # chargement de l'adresse de retour dans le registre $ra
	addiu $sp, $sp, 8     # on remet le pointeur de pile à sa position d'origine
	jr $ra