Algoritmos de búsqueda: colecciones, grafos y pathfinding con BFS, Dijkstra y A*

“Buscar” puede significar encontrar un registro en un array, comprobar una clave en un índice o descubrir una ruta entre estados. La palabra es la misma; la estructura, el costo y la garantía cambian por completo.

Binary Search no compite con A*. El primero reduce una colección ordenada. El segundo explora un grafo usando costos y una estimación hacia un objetivo. Antes de elegir un algoritmo, identifica la forma del problema.

Primero decide dónde estás buscando; después decide qué garantía necesitas.

01. Tres formas de buscar

La mayoría de los problemas de esta guía caen en tres familias:

Tres universos de búsqueda: colección, índice y grafo

Dentro de una colección importa si los datos están ordenados y cuántas consultas harás. Dentro de un grafo importan los pesos, el objetivo y la garantía esperada: alcanzar, recorrer, minimizar pasos o minimizar costo.

Una regla útil es medir el trabajo total, no solo una consulta:

costo total = preparación + cantidad de consultas × costo por consulta

Ordenar o construir un índice puede ser más caro que una búsqueda lineal. Compensa cuando reutilizas esa preparación o cuando el orden aporta otras operaciones, como rangos y límites.

02. Colecciones: recorrer, dividir o indexar

Comparación visual entre Linear Search, Binary Search y Map

Linear Search

Recorre hasta encontrar una coincidencia o terminar. Cuesta O(n) en el peor caso, usa O(1) espacio adicional y no exige preparación. Para una colección pequeña o una consulta aislada, suele ser la decisión más económica.

Binary Search

Compara con el punto medio y descarta la mitad imposible. Cada paso reduce el universo, por eso cuesta O(log n). Su precondición es el orden, y ese orden debe usar el mismo criterio que la búsqueda.

function binarySearch(values: number[], target: number) {
  let low = 0;
  let high = values.length - 1;

  while (low <= high) {
    const middle = low + Math.floor((high - low) / 2);
    const value = values[middle];

    if (value === target) return middle;
    if (value < target) low = middle + 1;
    else high = middle - 1;
  }

  return -1;
}

Binary Search también sirve como base de lowerBound y upperBound: encontrar el primer valor no menor o el primer valor mayor que un objetivo. Ahí el orden ofrece algo que un hash no puede dar directamente.

Map y Set

Un índice transforma consultas repetidas. Construirlo cuesta O(n) y memoria O(n), pero buscar una clave suele costar O(1) esperado:

const usersByEmail = new Map(users.map((user) => [user.email, user]));

const user = usersByEmail.get("ada@example.com");
const exists = usersByEmail.has("ada@example.com");

El intercambio es claridad: Map funciona para igualdad por clave; Binary Search conserva orden y permite rangos; Linear Search no prepara nada y acepta cualquier condición.

03. Grafos sin pesos: la frontera decide el recorrido

Un grafo representa nodos conectados: ciudades, pantallas, dependencias, celdas, estados o personas. Con una lista de adyacencia, BFS y DFS recorren O(V + E) porque visitan cada vértice y cada arista un número constante de veces.

Comparación de la frontera de exploración en BFS y DFS

La diferencia principal es la frontera:

BFS guarda niveles completos y puede usar más memoria en grafos anchos. DFS suele mantener una ruta activa, pero puede profundizar mucho y no garantiza el camino más corto.

Una implementación BFS necesita registrar padres, no solo nodos visitados, si quieres reconstruir la ruta:

function bfs(graph: Map<string, string[]>, start: string) {
  const queue = [start];
  const parent = new Map<string, string | null>([[start, null]]);

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head];

    for (const neighbor of graph.get(node) ?? []) {
      if (parent.has(neighbor)) continue;
      parent.set(neighbor, node);
      queue.push(neighbor);
    }
  }

  return parent;
}

Usar un índice head evita el desplazamiento repetido que produciría shift() en una cola grande.

04. Rutas con costo: Dijkstra y A*

Cuando las aristas tienen pesos, menos pasos ya no significa menor costo. Una ruta de tres segmentos puede ser más barata que una de dos.

Comparación visual entre Dijkstra y A* usando costo acumulado y heurística

Dijkstra expande siempre el nodo pendiente con menor costo acumulado. Con lista de adyacencia y una priority queue binaria, su costo habitual es O((V + E) log V). Requiere pesos no negativos: una arista negativa puede invalidar una distancia que ya parecía definitiva.

A* agrega una estimación hacia un objetivo:

f(n) = g(n) + h(n)

g(n): costo acumulado desde el origen
h(n): estimación restante hasta el objetivo

Si h(n) = 0, A* se comporta como Dijkstra. Una heurística útil puede evitar grandes regiones del grafo; una heurística débil explora más. Para preservar optimalidad, la estimación no debe sobrestimar el costo restante —y normalmente se usa una heurística consistente.

A* no es “Dijkstra rápido” por definición. La ganancia depende de la calidad y el costo de h(n), de la representación del grafo y de cuántos estados evita explorar.

05. Tabla de decisión y errores que invalidan la respuesta

Las equivocaciones importantes no son sintácticas; rompen precondiciones:

• Binary Search sobre datos que no respetan el orden del comparador.
• Crear un Map para una única consulta y ocultar su construcción y memoria.
• Usar DFS esperando el camino con menos pasos.
• Usar BFS cuando los costos de las aristas son distintos.
• Ejecutar Dijkstra con pesos negativos.
• Usar A* con una heurística que sobrestima y seguir esperando optimalidad.

06. Checklist para elegir

Antes de escribir código, responde:

1. ¿Buscas un elemento, una clave exacta o una ruta?
2. ¿Los datos ya están ordenados y necesitas rangos?
3. ¿Cuántas consultas reutilizarán la preparación?
4. ¿El grafo tiene pesos y pueden ser negativos?
5. ¿Quieres alcanzar, recorrer, minimizar pasos o minimizar costo?
6. ¿Existe un objetivo concreto y una heurística justificable?
7. ¿Necesitas reconstruir la ruta, no solo saber que existe?

Empieza con la estructura más simple que sostenga la garantía. Linear Search es correcto cuando preparar más cuesta demasiado; Binary Search cuando el orden importa; Map cuando una clave se consulta repetidamente; BFS y DFS cuando importan relaciones sin costo; Dijkstra y A* cuando la ruta debe optimizarse.

La pregunta final no es “¿qué búsqueda es más rápida?”. Es “¿qué universo estoy explorando y qué significa una respuesta correcta?”.