¿Qué es Binary Search?

El algoritmo Binary Search (búsqueda binaria) es una técnica eficiente para encontrar un elemento dentro de un arreglo ordenado. Su funcionamiento se basa en dividir el arreglo en dos mitades y descartar la mitad que no contiene el elemento objetivo en cada iteración.

El Código

                    
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    console.log(
      `left: ${left}, mid: ${mid}, right: ${right}, arr[mid]: ${arr[mid]}`
    );

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // Elemento no encontrado
}

// Ejemplo de uso
const array = [2, 3, 4, 10, 40];
const target = 10;
console.log("Arreglo inicial:", array);
const result = binarySearch(array, target);
console.log(
  result !== -1
    ? `Elemento encontrado en el índice ${result}`
    : "Elemento no encontrado"
);
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo ordenado (arr) y un valor objetivo (target).
• Salida: El índice del elemento encontrado o -1 si no se encuentra el elemento.
• Complejidad: O(log n), ya que reduce a la mitad el rango de búsqueda en cada iteración.
• Método: Divide y conquista:
  • Calcula el índice medio: mid = Math.floor((left + right) / 2).
  • Compara el elemento del medio con el objetivo.
  • Ajusta los límites (left, right) según sea necesario.
• Limitación: Requiere que el arreglo esté previamente ordenado.

Uso Práctico

El código es ideal para aplicaciones donde se necesita realizar búsquedas rápidas, como:

• Índices en bases de datos.
• Buscadores en listas ordenadas (e.g., directorios de nombres).
• Sistemas que manejan grandes cantidades de datos ya clasificados.

Ejemplo de Ejecución

Arreglo inicial: [10, 20, 30, 40, 50, 60, 70, 80]

Proceso de búsqueda:

1. Iteración 1:
   • Índices: left = 0, right = 7, mid = 3
   • Valor en arr[mid] = 40
   • Comparación: 40 < 50. Actualizar left = 4.
2. Iteración 2:
   • Índices: left = 4, right = 7, mid = 5
   • Valor en arr[mid] = 60
   • Comparación: 60 > 50. Actualizar right = 4.
3. Iteración 3:
   • Índices: left = 4, right = 4, mid = 4
   • Valor en arr[mid] = 50
   • Comparación: 50 === 50. ¡Elemento encontrado!

Resultado: El índice del elemento 50 es 4.

Información Adicional

La búsqueda binaria es un algoritmo muy utilizado en informática por su eficiencia en comparación con la búsqueda lineal. Su uso es común en estructuras de datos como árboles binarios y bases de datos indexadas.