Búsqueda Binaria

La búsqueda binaria es elegantemente simple: compara el elemento del medio con tu objetivo; si el objetivo es menor, descarta la mitad derecha; si es mayor, descarta la mitad izquierda. Repite hasta encontrarlo o agotar el espacio de búsqueda. O(log n) significa que en 1 millón de elementos solo necesitas máximo 20 comparaciones.

Requiere que el array esté ordenado, pero si puedes ordenarlo una vez y buscar muchas veces, vale totalmente la pena.

La búsqueda binaria es mucho más versátil que buscar en un array ordenado.

Se puede aplicar al "espacio de búsqueda" de cualquier problema donde la respuesta es monótona: "¿cuál es el mínimo valor de X que cumple esta condición?" Si para valores bajos de X la condición es false y para altos es true (o viceversa), puedes hacer búsqueda binaria sobre X.

Ejemplos: encontrar el primer elemento mayor a N, mínima velocidad para llegar a tiempo, capacidad mínima de un camión.

// Búsqueda Binaria clásica
function busquedaBinaria(arr, objetivo) {
  let izq = 0, der = arr.length - 1;
  
  while (izq <= der) {
    const mid = Math.floor((izq + der) / 2);
    if (arr[mid] === objetivo) return mid;
    if (arr[mid] < objetivo) izq = mid + 1;
    else der = mid - 1;
  }
  return -1;
}

// Primera posición del objetivo (si hay duplicados)
function primeraPosicion(arr, objetivo) {
  let izq = 0, der = arr.length - 1, resultado = -1;
  while (izq <= der) {
    const mid = Math.floor((izq + der) / 2);
    if (arr[mid] === objetivo) {
      resultado = mid;
      der = mid - 1; // Seguir buscando a la izquierda
    } else if (arr[mid] < objetivo) {
      izq = mid + 1;
    } else {
      der = mid - 1;
    }
  }
  return resultado;
}

// Búsqueda binaria en el "answer space"
// Problema: mínimo número de días para leer todos los libros
// donde cada día puedes leer hasta "capacidad" páginas
function minimosDias(paginas, capacidad) {
  let izq = capacidad, der = paginas.reduce((a, b) => a + b);
  let resultado = der;
  
  while (izq <= der) {
    const mid = Math.floor((izq + der) / 2);
    
    if (puedeTerminar(paginas, mid)) {
      resultado = mid;
      der = mid - 1; // Intentar menos tiempo
    } else {
      izq = mid + 1;
    }
  }
  return resultado;
}

function puedeTerminar(paginas, maxPorDia) {
  let dias = 1, hoy = 0;
  for (const p of paginas) {
    if (hoy + p > maxPorDia) { dias++; hoy = 0; }
    hoy += p;
  }
  return dias <= maxPorDia;
}