↓Ir al contenido
  1. Blog/

#Algoritmos: Búsqueda binaria

·4 mins·
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos.
Tabla de contenido

Directorio teléfonico #

Imagina que tienes en las manos un directorio teléfonico de los años 90 y tienes que buscar el número de teléfono de un amigo. Es importante tener en cuenta que los contactos están ordenados alfabéticamente en estos casos. Es este hecho es el enfoque de nuestra entrada hoy.

Suponiendo que buscamos el número teléfonico de Juan, ¿Tiene sentido empezar desde las primeras páginas dónde estarán los números de personas cómo Alberto o Alejandra? Claro que no, será muchísimo más fácil identificar en qué parte el directorio se listan esos contactos cuyos nombres inician con J. sin embargo, siguen siendo muchos contactos y encontrar esta letra específicamente podría tomarnos una, dos, o n intentos.

Una mejor manera de abordarlo sería abrir este directorio justo por la mitad, ya que los contactos están ordenados, podemos identificar si nuestra letra objetivo estará a la izquierda o a la derecha. Suponiendo que a la mitad de este directorio se encuentra la letra M, hemos reducido nuestro espacio de búsqueda efectivamente a la mitad a la izquierda. Esta idea puede aplicarse una vez encontremos la sección de las Js, y así sucesivamente hasta encontrar a Juan.

Quiero ver código #

Han pasado años desde la última vez que ví un directorio teléfonico, sino es en películas de los 90s, así que vamos a ver un ejemplo más acorde a lo que sabemos hacer aquí. Para ello, validaremos si un número X está incluído dentro de una lista de N elementos.

En el ejemplo, mencionamos que el aspecto más importante era que los contactos estén ordenados. Esto es así, porque es la única forma en la que podemos reducir nuestro espacio de búsqueda por la mitad teniendo la certeza de que todos los valores a la derecha y a la izquierda serán mayores y menores, respectivamente, al valor que decidimos usar como referencia (la mitad).

Esta será nuestra lista de trabajo:

const numbers = [2, 3, 5, 9, 15, 17, 55, 69];

Para ejecutar de manera efectiva el algoritmo, necesitaremos identificar el mayor y menor número en nuestra lista, para eso usaremos estos indices:

let maxIndex = numbers.length - 1;
let minIndex = 0;

Con este código identificaremos la mitad de nuestra lista:

let half = Math.floor((minIndex + maxIndex)/2);

Y ahora así, miremos cómo aplicar este algoritmo en código:

const find = 17;
const numbers = [2, 3, 5, 9, 15, 17, 55, 69];

function busquedaBinaria(collection, findee) {
  // Asignando los valores del rango inicial
  let minIndex = 0;
  let maxIndex = numbers.length - 1;

  while (minIndex <= maxIndex) {
    
    // Calculando la posición en el medio de la lista
    let half = Math.floor((minIndex + maxIndex) / 2);

    // Recoger el valor del medio
    let guess = collection[half];

    if (guess === findee) // Comparamos si es el valor que buscamos
      return half;

    else if (guess > findee) 
      // Si el valor que buscamos es menor al valor supuesto
      // debemos reducir nuestro rango de búsqueda.
      // Ahora nuestro mayor valor está justo debajo de la mitad calculada.
      maxIndex = half - 1; 
    
    else 
      // Si el valor que buscamos es mayor al valor supuesto
      // debemos reducir nuestro rango de búsqueda.
      // Ahora nuestro menor valor está justo arriba de la mitad calculada.
      minIndex = half + 1;
  }
  return -1;
}

const foundIndex = busquedaBinaria(numbers, find);
console.log(
  foundIndex === -1
    ? `El número ${find} no fue encontrado.`
    : `El número ${find} está en el índice ${foundIndex}.`
);

Es esta dinámica de decidir únicamente entre dos opciones, cada vez que reducimos el área de búsqueda, lo qué le da su nombre al algoritmo.

Conclusión #

Podríamos haber simplemente ejecutado el siguiente código:

const find = 17;
const numbers = [2, 3, 5, 9, 15, 17, 55, 69];

let foundIndex = -1;

for (let index = 0; index < numbers.length; index++) {
  if (find === numbers[index]) {
    foundIndex = index;
    break;
  }
}

console.log(
  foundIndex === -1
    ? `El número ${find} no fue encontrado.`
    : `El número ${find} está en el índice ${foundIndex}.`
);

Comparar cada uno de los items en la lista y, cuando lo encontramos, listo. Podrías pensar que es enfoque es muchísimo más fácil y rápido de programar, y tienes razón. Pero, ¿Qué pasa cuando nuestra lista no contiene 8 items sino 1,000,000?

La intención de este post es mostrarte que, si bien es cierto en programación hay muchas formas de resolver un problema, nuestro objetivo conforme avanzamos en nuestra carrera es escogar la más óptima. Cada problema es un mundo y es nuestro trabajo encontrar la mejor solución.

Referencias #

↑