Ir al contenido principal

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.








Comentarios

Entradas populares de este blog

Follow up Java.

Java: So far, so good! A poco más de 20 días de una nueva aventura profesional, la perspectiva de aprovechamiento, tiempos de aprendizaje y transferencia del conocimiento ha sido interesante, en realidad muy positiva. Después de casi 3 semanas de haber comenzado,  el aprendizaje de los conceptos base (knowledge base, término ampliamente utilizado en el área),  la familiarización con la estructura del código, la codificación en sí, comienzan a dar frutos y a tomar forma. ¿Qué hemos aprendido hasta el momento? Estructura del lenguaje Tipos de variables, variables de miembros y cómo declararlas Uso de operadores y concepto de operandos Estructura básica de las clases, objetos, interfaces, packages Herencia de objetos, instancias, atributos estáticos, parámetros, variables, métodos Entre otros temas, esos son los avances. En retrospectiva, el bagaje de conocimiento  previo  (en lo personal)    ha sido de gran impacto en términos positivos y la curva de aprendizaje mu

Finalmente me encontré con ella y desde el día #1, hemos disfrutado juntos...

Hace más de 4 años que nos mirábamos, pero nos ignorábamos, fue quizá por que no era el momento, yo tenía una relación más dinámica, más demandante, más intensa, sin embargo en ese lapso de 4 años si tuve 3 encuentros con la que hoy ahora comienzo a sentirme entregado: Yoga He hecho Crossfit por mucho tiempo, lo he amado, y me he entregado al 100%, ese ha sido mi receso del día en una vida adulta. En el lapso de los últimos 4 años, un amigo -colombiano por cierto- me invitó a su casa a hacer yoga, él en ese tiempo era maestro de yoga en un pequeño pueblo pegado al mar en las costas de Quintana Roo. Tomé 3 clases con él, y desde la primera, quedé enamorado, sabía que quería intentarlo pero estaba concentrado en un ejercicio de más alto impacto, supongo que la edad también juega un factor importante, al menos eso pienso. Hoy con el contexto que hemos estado viviendo, el encierro y aislamiento principalmente, nuestro reto más importante, toca reconfigurarse a si mismo, probar nuevos campo