Algoritmos en ciencias de la computación, parte 1: búsquedas binarias

En la práctica los algoritmos nos ayudan a resolver problemas en diferentes escalas de complejidad y para diferentes situaciones, es por ello que vale la pena revisar y sobre todo practicarlos regularmente, todo con la finalidad de fortalecer nuestro entendimiento y sobre todo nuestra habilidad de resolver problemas y también mejorar la calidad de nuestro código fuente, independientemente del lenguaje de programación que utilicemos.

En esta ocasión revisaremos con detalle uno de los métodos de búsquedas más utilizados y estudiados en las ciencias de la computación.

El método de búsquedas binarias se utiliza mucho en situaciones en donde requieres hacer búsquedas de manera eficiente y sobre todo rápidas, es por ello que analizaremos un ejemplo y correremos algunas pruebas (en mi caso utilizaré Python, sin embargo intentaré compartirles la versión en Java posteriormente).

Imaginemos el siguiente ejemplo:

Dada una lista de número aleatorios ordenados de forma ascendente:

numbers: list[Any] = [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77]

Tenemos veinte valores donde el número 1 comienza en el índice mínimo 0, y el último valor, 77 termina en el índice máximo 19.

Supongamos que el número o valor que queremos encontrar dentro de la lista de valores es el número 33, llamémosle objetivo.

Si deseáramos aplicar el algoritmo de búsqueda binaria tendríamos que programar el siguiente pseudo código:

1. Definimos el índice mínimo de la lista en 0, y el índice máximo a n-1, en donde n-1 es el número índice máximo que contiene el valor 77. Recordemos que en esta lista tenemos 20 valores, sin embargo puesto que vamos a recorrer la lista a través de los índices, y el índice mínimo comienza en 0, entonces el índice máximo tendría que ser el tamaño de la lista - 1 (es decir, n-1 = 19).
2. Si el índice máximo es menor que el índice mínimo, entonces detenemos el algoritmo ya que el número que estamos buscando no existe dentro de la lista.
3. Calculamos el promedio del índice mínimo y el índice máximo y lo dividimos entre 2, lo podemos llamar índice salto.
4. Validamos si el valor que contiene el índice salto es igual al valor objetivo que buscamos. Si es verdadero, entonces hemos encontrado el número y hemos terminado.
5. Si el valor situado en el índice salto es menor que el valor objetivo, entonces reasignamos el valor del índice mínimo a índice salto - 1
6. Si el valor situado en el índice salto es mayor que el valor objetivo, entonces reasignamos el valor del índice máximo a índice salto + 1
7. Regresamos al paso número 2 de este pseudo código.

¿Qué podemos deducir de esta receta?, expliquemos en términos generales lo que sucede.

El algoritmo intenta hacer la búsqueda de la manera mas eficiente para este tipo de circunstancias, es decir, toma una lista de valores, suma el índice mínimo con el índice máximo y lo divide entre 2, y dependiendo de si el valor en el índice salto resultante es mayor o menos, se mueve a la izquierda o derecha, desechando prácticamente la mitad de los números de la lista en cada iteración. La idea es llegar al número en el menor número de iteraciones posibles.

Ahora veamos la implementación del código en Python.

# Tenemos una lista de valores númericos. La lista contiene 20 valores, pero no confundamos los valores con los índices o pivotes que nos servirán para movernos en la lista hasta encontrar nuestro valor.

numbers: list[Any] = [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77]

# Inicializamos el índice mínimo a 0

min_index: int = 0

# Inicializamos el índice máximo a n-1, que dada nuestra lista, sería 19, el último índice o índice máximo.

max_index: int = len(numbers) - 1

# Inicializamos una variable boleana para controlar nuestro bucle while, le asignamos el valor False.

found_it: bool = False

# Para observar y entender mejor el algoritmo, vale la pena llevar un control del número de movimientos que hace el algoritmo hasta encontrar el valor objetivo.

movements: int = 0

# Asignamos el valor objetivo

target: int = 33

# Para efectos de monitorear y entender mejor, también exponemos los valores iniciales.

print(f"numbers: {numbers}, \nmin_index: {min_index}, \nmax_index: {max_index}, \ntarget: {target}\n")

# Creamos un bucle while para recorrer nuestra lista y en tanto nuestra variable boleana no sea True, el bucle seguirá hasta que se complete algunas de las condicionantes que hay en el interior.

while found_it is False:

                # Si por alguna razón el valor objetivo dentro de la lista no existe, lo sabremos.
		if max_index < min_index:
			print(f"The number is not in the list!\n")
			break

                # Calculamos nuestro índice salto
		guess = int((min_index + max_index) / 2)

                # Si el valor que contiene nuestro índice salto es igual al valor objetivo, entonces hemos terminado.
		if numbers[guess] == target:
			print(f"We get the prom based on: guess = int((min_index + max_index) / 2). We found the number: {target} in index {guess}, numbers[guess] is {numbers[guess]}\n")
			found_it = True

                # Si la condición anterior no sucedió, entonces preguntamos si el índice salto es menor que el valor objetivo, si es así, reasignamos el índice menor con el índice salto + 1
		elif numbers[guess] < target:
			print(f"guess is {guess}. We move the min_index = guess + 1. So min_index becomes {guess + 1} and max_index still: {max_index}\n")
			min_index = guess + 1

                # Si no sucedieron ninguna de las dos condiciones anteriores entonces el índice salto es mayor que el valor objetivo, por lo tanto reasignamos el índice máximo con el índice salto - 1
		else:
			print(f"guess is {guess}. We move the max_index = guess -1. So max_index becomes {guess - 1}, and min_index still: {min_index}\n")
			max_index = guess - 1

                # Contabilizamos los movimientos que efectuamos 
		movements+=1

		print(f"movement number: {movements}\n")

        # Para efectos de entender mejor el algoritmo, imprimimos el estado final de cada una de las variables del algoritmo.
	print(f"movements: {movements}, min_value: {min_index}, max_index: {max_index}, target: {target}\n

Puede resultar un poco complejo entender el concepto de los algoritmos pero eso no significa que no podamos entenderlos en algún punto después de estudia y estudiar. Te recomiendo que primero intentes entender el concepto de los algoritmos y luego pongas en practica lo aprendido.