/Tecnología

Algoritmos | La búsqueda binaria

La búsqueda binaría es uno de los algoritmos estrella en las entrevistas de trabajo pero también muy útil en la vida diaria cuando tenemos que encontrar cosas, primero quiero hablar de dos formas previas para encontrar cosas que son la enumeración exhaustiva y la aproximación de soluciones.

Te platico algo que me pasó, mi esposa llegó diciéndome que había comprado algo para nuestro perro a un “super precio” y al preguntarle cuanto costó me dijo la frase que muchos ya conocemos: “a ver, adivina”, lo cuál hace que echemos números al aire esperando dar con la respuesta.

Ante ese escenario tenía 3 estrategias: enumeración exhaustiva, la aproximación de soluciones y la búsqueda binaría, así que te platico que pasa en las dos primeras y cómo lo resolví con la tercera.

Enumeración exhaustiva

En esta forma yo tengo que probar cada elemento de la solución posible, en este caso, a mi esposa le costó 210 pesos, si yo aplico la enumeración exhaustiva la charla hubiera sido algo así:

  • Yosh: 1 peso?
  • Esposa: no, más!
  • Yosh: 2 pesos?
  • Esposa: mmm no…
  • Yosh: 3 pesos?
  • Esposa: Vas a seguir así? Olvídalo, mejor me voy a ver Netflix
  • Yosh: 4 pesos?

Digamos que pude haber desesperado a mi esposa a los 45 pesos y haber sabido que costó 210 por confesión de ella, pero las máquinas no se desesperan y hubieran probado cada solución hasta que el resultado fuera válido, es decir, 210 intentos.

Aproximación de soluciones

En esta pude decidir que iba a probar valores en un rango, por ejemplo, de 50 en 50 pesos, el problema de la aproximación esta en su nombre… es aproximado y si el número o el valor del rango que eliges es muy pequeño vas a tardar más en llegar a una solución correcta pero ganarás más precisión, pero si el rango es muy grande, perderás precisión pero ganarás velocidad.

Ejemplo:

Mi esposa gastó 210 pesos, y yo decidí probar valores de 100 en 100 pesos:

  • Yosh: 100 pesos
  • Esposa: No, más
  • Yosh: 200 pesos
  • Esposa: ya estás muy cerca!!!
  • Yosh: 300 pesos
  • Esposa: menos!!!
  • Yosh: 200 pesos
  • Esposa: Más!
  • Yosh: 300 pesos!
  • Esposa: Qué no!!!
  • Yosh: Pues entonces como entre 200 y 300 pesos…

Imagínate ese ejemplo pero si hubiera probado con valores de 10 en 10 o de 5 en 5, seguramente habría dado con la respuesta correcta pero me habría tardado más.

Búsqueda binaría

Esta solución consiste en partir el problema en mitades, es como cuando buscas algo en el diccionario, llegas a la sección donde está la letra que buscas y revisas la mitad de la sección a ver si esta ahí, y dependiendo de donde esté te mueves una mitad más adelante o más atras dependiendo de lo que buscas, al igual que cuando vas a la biblioteca.

Aquí digamos que hice un poco de trampa y asumí que lo más que se pudo gastar en nuestro perrito fueron quinientos pesos en un arrebato capitalista, entonces aplicando una aproximación de la búsqueda binaría de partir el problema en mitades la charla fue así:

  • Yosh: 500 pesos?
  • Esposa: no, menos
  • Yosh: 250 pesos?
  • Esposa: menos!
  • Yosh: 125 pesos?
  • Esposa: más!
  • Yosh: 187 pesos?
  • Esposa: más!
  • Yosh: 218?
  • Esposa: menos
  • Yosh: 203?
  • Esposa: más!
  • Yosh: 211?
  • Esposa: menos
  • Yosh: 207?
  • Esposa: más
  • Yosh: 209?
  • Esposa: más
  • Yosh: 210?
  • Esposa: Sí!!!!

Si vez, aquí gané en precisión, velocidad y no tuve que probar cada solución, sino que al partir el problema en mitades (aquí aproximadas, debo reconocer) dí con el valor correcto y no desesperé tanto a mi esposa, este mismo enfoque puede aplicarse en algoritmos computacionales; sólo hay un requisito, los datos que buscas deben estar ordenados, de lo contrario esta técnica no funcionará y tendrás que hacer enumeración exhaustiva, al igual que cuando armas un rompecabezas, cuando buscas una pieza de lego entre muchas otras del mismo color o cuando buscas la pareja entre tus calcetines.

Espero que esta explicación te haya ayudado a entender mejor este algoritmo.

Yoshua Díaz

Yoshua Díaz

FullStack Dev | Escritor | Creativo | Comediante | Introvertido Excéntrico

Leer más