	.data
A:      .word 2, 12, 20, 25, 34, 40, 54, 76
n:	.word 8			# Número de elementos
x:	.word 0			# Variable a buscar
m1:	.asciiz "Escribe el número a buscar: "
m2: .asciiz "El número no está."
m3: .asciiz "El número si está."

	.text

	la $a0, m1
	li $v0, 4 # print_str
	syscall

	li $v0, 5 # read_int
	syscall
	la $t0, x		# t0 apunta a x
	sw $v0, ($t0)		# guarda v0 en x

# Llama a la búsqueda binaria
	la $a0, A		# dirección del arreglo
	la $a1, n		# tamaño del arreglo
	la $a2, x		# direccion del número a buscar
	jal bus_bin

# Escribe el resultado
	move $t0, $v0		# t0 = v0
	beq $t0, $zero, no_esta	# if (t0 == 0) goto no_esta
	la $a0, m3		# a0 apunta al string "si esta"
	j imprime

no_esta:
	la $a0, m2		# a0 apunta al string "no esta"

imprime:
	li $v0, 4		# print_str
	syscall

# The program is finished. Exit.
	li $v0, 10          	# system call for exit
	syscall               	# Exit!

#
# bus_bin - búsqueda binaria
#
# Registros usados:
#
# + Entrada:
#		$a0 - dirección del arreglo
#		$a1 - dirección del tamaño del arreglo
#		$a2 - dirección del número a buscar
#
# + Salida:
#		$v0 - 1 (éxito) o 0 (falla)
#
# + Internos:
#		$t0 - inicio
#		$t1 - final
#		$t2 - dato
#		$t3 - medio
#		$s0 - temporal
#
# Algoritmo empleado:
#
# int bus_bin(int dato, int array[], int tamaño)
# {
#      int inicio = 0;
#      int final = tamaño - 1;
#      while (inicio <= final) {
#          int medio = (inicio + final)/2;
#          if (dato == array[medio])
#              return 1;  // exito
#          else if (dato > array[medio])
#              inicio = medio + 1;
#          else
#              final = medio - 1;
#      }
#      return 0; // falla
#  }
#

bus_bin:

	# inicializa variables
	li $t0, 0			# inicio = 0

	lw $t1, ($a1)
	addi $t1, $t1, -1		# final = n - 1

	lw $t2, ($a2)			# dato = memoria[a2]

ciclo:
	bgt $t0, $t1, falla		# if inicio > final goto falla

	add $t3, $t0, $t1		# medio = inicio + final
	srl $t3, $t3, 1			# medio = medio / 2

	move $s0, $t3			# s0 = medio
	sll $s0, $s0, 2			# s0 *= 4 (s0 tiene el offset del elemento medio)
	add $s0, $a0, $s0		# s0 apunta al elemento medio (base + offset)
	lw $s0, 0($s0)			# s0 = arreglo[medio]

	beq $t2, $s0, exito		# if (dato == arreglo[medio]) goto exito
	bgt $t2, $s0, mayor		# if (dato > arreglo[medio]) goto mayor

	move $t1, $t3			# final = medio
	addi $t1, $t1, -1		# final--
	j ciclo				# regresa al while

mayor:
	move $t0, $t3			# inicio = medio
	addi $t0, $t0, 1		# inicio++
	j ciclo				# regresa al while

exito:
	li $v0, 1			# return 1
	j regresa

falla:
	li $v0, 0			# return 0

regresa:
	jr $31				# regresa

