Algoritmo de búsqueda: definición, tipos y ejemplos (lineal, binaria, hash)

Un algoritmo de búsqueda es un método para encontrar un valor objetivo dentro de una lista. Comprueba cada elemento de la lista en busca del valor objetivo hasta encontrar una coincidencia o hasta que se hayan buscado todos los elementos.

La búsqueda lineal no suele ser práctica porque otros algoritmos y esquemas de búsqueda, como el algoritmo de búsqueda binaria y las tablas hash, permiten una búsqueda mucho más rápida para todas las listas, excepto las cortas.

¿Qué es un algoritmo de búsqueda?

Un algoritmo de búsqueda es una rutina que, dado un conjunto de datos (por ejemplo, un arreglo, una lista enlazada o una estructura más compleja), localiza la posición o confirma la presencia/ausencia de un elemento que cumpla cierta condición (usualmente igualdad con un valor objetivo). Los algoritmos de búsqueda se evalúan por su complejidad temporal (cuánto tarda) y su complejidad espacial (memoria adicional que necesitan).

Tipos principales y ejemplos

Búsqueda lineal (secuencial)

La búsqueda lineal recorre los elementos uno por uno desde el principio hasta el final, comparando cada elemento con el valor buscado.

Ejemplo de proceso:

Tomar el primer elemento. Si es igual al objetivo, detener y devolver la posición.
Si no, pasar al siguiente elemento y repetir.
Si se llega al final sin encontrarlo, devolver "no encontrado".

Complejidad:

Tiempo promedio: O(n)
Peor caso: O(n)
Espacio adicional: O(1)

Ventajas y desventajas:

Ventaja: funciona en listas sin ordenar y es simple de implementar.
Desventaja: ineficiente para listas grandes.

Búsqueda binaria

La búsqueda binaria es mucho más rápida, pero requiere que la lista esté ordenada. Divide repetidamente el intervalo de búsqueda por la mitad comparando el elemento central con el objetivo.

Pasos básicos:

Comparar el objetivo con el elemento del medio.
Si coinciden, devolver la posición.
Si el objetivo es menor, repetir en la mitad izquierda; si es mayor, en la mitad derecha.
Si el intervalo queda vacío, devolver "no encontrado".

Complejidad:

Tiempo promedio y peor caso: O(log n)
Espacio adicional: O(1) (iterativa) o O(log n) (recursiva, por la pila)

Notas importantes:

Requiere que los datos estén ordenados; si no lo están, el coste de ordenar (por ejemplo O(n log n)) puede hacer que la binaria no sea rentable para búsquedas únicas.
Es adecuada cuando se realizan muchas búsquedas sobre una misma colección ordenada.

Ejemplo sencillo:

Lista ordenada: [2, 5, 9, 14, 20]; buscar 9 → comparar con elemento medio (9) → encontrado.

Tablas hash

Las tablas hash (o tablas de dispersión) almacenan pares clave-valor y usan una función hash para mapear una clave a una posición en una estructura de almacenamiento. Permiten búsquedas muy rápidas en promedio.

Características:

Tiempo promedio de búsqueda: O(1)
Peor caso: O(n) (si muchas claves colisionan y la resolución es ineficiente)
Requieren memoria adicional para la tabla y, en muchos casos, redimensionado dinámico cuando crecen.

Resolución de colisiones:

Encadenamiento: cada posición guarda una lista de elementos que colisionan.
Dirección abierta / open addressing: las entradas colisionadas se colocan en otra posición siguiendo alguna estrategia (por ejemplo, sondeo lineal, doble hashing).

Ventajas y desventajas:

Ventaja: búsquedas, inserciones y eliminaciones muy rápidas en promedio.
Desventaja: no mantienen orden de elementos y pueden consumir más memoria; el rendimiento depende de la calidad de la función hash y de la carga (load factor).

Comparación rápida y cuándo usar cada uno

Búsqueda lineal: cuando la lista es pequeña, está desordenada y no compensa ordenar; o cuando los datos llegan en flujo y no hay estructura adicional.
Búsqueda binaria: cuando los datos están ordenados (o es barato mantenerlos ordenados) y se realizan muchas búsquedas.
Tablas hash: cuando se necesita acceso rápido (por clave) sin importar el orden, y se puede asignar memoria adicional para la estructura.

Ejemplos prácticos

1) Búsqueda lineal: buscar el nombre de una persona en una lista corta de contactos impresos.

2) Búsqueda binaria: buscar un número telefónico en una guía telefónica ordenada por apellidos.

3) Tablas hash: implementar un diccionario (clave → definición) en un lenguaje de programación para consultas frecuentes.

Conclusión

No existe un único algoritmo de búsqueda ideal para todas las situaciones. La elección depende del tamaño de los datos, si están ordenados, la frecuencia de búsquedas frente a actualizaciones y las restricciones de memoria. Comprender las propiedades (complejidad, requisitos y comportamiento práctico) de la búsqueda lineal, binaria y basada en tablas hash permite seleccionar la opción más eficiente para cada caso.