Búsqueda Eficiente: Búsqueda Binaria y Más Allá

La búsqueda es la base de los algoritmos. Mientras que la búsqueda lineal es $O(n)$, la Búsqueda Binaria nos permite encontrar elementos en $O(\log n)$ reduciendo repetidamente el espacio de búsqueda a la mitad.

1. Búsqueda Binaria Clásica

Se utiliza para encontrar un valor en un arreglo ordenado.

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // Evitar (left + right) / 2 para prevenir desbordamiento en algunos lenguajes
    const mid = Math.floor(left + (right - left) / 2);

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

  return -1;
}

[!WARNING] Desbordamiento de Pila / Precisión: En JavaScript, los números son flotantes de 64 bits, por lo que $2^{53}-1$ es el límite para enteros seguros. En lenguajes como Java o C++, (left + right) / 2 puede desbordar un int. Usar left + (right - left) / 2 es una mejor práctica universal.

2. Búsqueda en una Matriz 2D Ordenada

Esta matriz tiene dos propiedades:

1. Cada fila está ordenada.
2. El primer elemento de cada fila es mayor que el último elemento de la fila anterior.

Esto significa que toda la matriz actúa como un solo arreglo ordenado.

/**
 * Busca eficientemente un valor en una matriz m x n ordenada.
 * Complejidad de Tiempo: O(log(m * n))
 */
function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) return false;

  const rows = matrix.length;    // Número de filas (arreglos externos)
  const cols = matrix[0].length; // Número de columnas (tamaño de arreglos internos)
  let left = 0;
  let right = rows * cols - 1;

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    // Convertir índice 1D de nuevo a coordenadas 2D
    const midValue = matrix[Math.floor(mid / cols)][mid % cols];

    if (midValue === target) {
      return true;
    } else if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

[!TIP] Truco del Arreglo Virtual: Cuando una matriz 2D está completamente ordenada (como en este caso), no busques fila por fila. Trátala como un arreglo 1D “virtual”. El índice i se mapea a matrix[Math.floor(i / cols)][i % cols].

Lista de Verificación para la Condición de Búsqueda

Si te preguntas si puedes usar la Búsqueda Binaria, pregúntate:

• ¿Están los datos ordenados?
• ¿Puedo descartar la mitad del espacio de búsqueda basándome en un elemento central?
• ¿Puedo encontrar un límite superior o inferior?

Consejo de Eficiencia para Entrevistas

Si los datos no están ordenados, generalmente ordenarlos toma $O(n \log n)$ y luego la búsqueda binaria toma $O(\log n)$. Total: $O(n \log n)$. ¡Si solo buscas una vez, una simple búsqueda $O(n)$ es en realidad más rápida! Solo usa la Búsqueda Binaria en datos no ordenados si planeas buscar varias veces.