6 Tipos de algoritmos de búsqueda y cómo funcionan

Puedes imaginar los algoritmos de búsqueda como detectives digitales, encontrando lo que necesitas en vastas colecciones de datos, como sitios web o bases de datos, con el menor número de pasos posible.

Desde Google y Amazon hasta Facebook y Netflix, los algoritmos de búsqueda juegan un papel vital en las interacciones digitales en la vida cotidiana.

En este artículo, aprenderás sobre los tipos más comunes de algoritmos de búsqueda, sus complejidades de tiempo, cómo funcionan sus procesos de búsqueda y aplicaciones en la vida real en informática.

Una menor complejidad media de los casos es mejor para un rendimiento más rápido, especialmente con entradas grandes. Algoritmos como la búsqueda binaria O(log n) son muy eficientes.

Por otro lado, complejidades mayores, como O(n), pueden resultar poco prácticas para grandes bases de datos debido al crecimiento lineal o peor del tiempo de ejecución. Sin embargo, la eficiencia también depende de factores como el contexto del problema, los recursos y los requisitos de aplicación.

1. Algoritmo de búsqueda lineal

La búsqueda lineal, también conocida como búsqueda secuencial, itera a través de cada elemento de la matriz, comparándolo con el elemento objetivo hasta que encuentra una coincidencia. Si la función de búsqueda llega al final de la matriz sin encontrar ninguna coincidencia, indica que el elemento objetivo no está presente en el conjunto de datos.

El elemento buscado puede ser un número, una cadena, un objeto o cualquier otro tipo de dato que pueda almacenarse en una matriz. Esta flexibilidad hace de la búsqueda lineal un algoritmo versátil que puede aplicarse a una amplia gama de tipos de datos.

Para ilustrar mejor este proceso de búsqueda, veamos un ejemplo de la vida real.

Supongamos que tienes una lista sin ordenar de números enteros que representan las edades de las personas de un grupo. Se te pide que averigües si una edad específica, digamos 25, está presente en la matriz. Empezarías por el principio de la matriz y comprobarías cada elemento, uno a uno, hasta encontrar la edad 25 o llegar al final de la matriz.

El tiempo de ejecución de un algoritmo de búsqueda lineal es proporcional al tamaño de la matriz. La complejidad computacional de la búsqueda lineal es O(n), donde n es el número de elementos de la matriz.

Aplicaciones de la búsqueda lineal

• Tareas de búsqueda sencillas: La búsqueda lineal suele utilizarse para un amplio espectro de tareas de búsqueda básicas en las que el conjunto de datos es pequeño o en las que no se justifica la complejidad adicional de otros algoritmos. Por ejemplo, para buscar en una pequeña lista de nombres o números.
• Estructuras de datos lineales: La búsqueda lineal es fundamental para muchas estructuras de datos lineales, como matrices, listas y pilas. Se suele utilizar para explorar estas estructuras con el fin de localizar elementos específicos o realizar operaciones.
• Matrices desordenadas: Dado que la búsqueda lineal comprueba cada elemento secuencialmente, puede localizar elementos independientemente de su posición en la matriz.

2. Algoritmo de búsqueda binaria

La búsqueda binaria es un algoritmo eficaz utilizado para encontrar un valor objetivo dentro de una lista ordenada. Divide repetidamente el intervalo de búsqueda por la mitad utilizando el método de búsqueda binaria. Después, comprueba el valor objetivo con el elemento central y procede hacia la parte derecha o izquierda de la matriz. Este proceso continúa hasta que se encuentra el valor objetivo. Alternativamente, el intervalo de búsqueda aparece vacío cuando el objetivo no está presente en la matriz.

Veamos un ejemplo de utilización de la búsqueda binaria para encontrar un valor numérico específico.

Imagina que tienes una matriz de números: [2,5,8,12,16,23,38,56,72,91], y quieres encontrar el número 23.

Se empieza por el elemento central (nodo raíz), que es 16. Como 23 es mayor que 16, sólo se miran los números a la derecha de 16. A continuación, se observa el elemento central de esta parte, que es 56. Como 23 es menor que 56, sólo se observan los números situados a la derecha de 16. Como 23 es menor que 56, sólo se miran los números a la izquierda de 56. Ahora miras de nuevo el elemento central, que es 23. ¡Has encontrado la clave de búsqueda!

El tiempo de ejecución de un algoritmo de búsqueda binaria es O (log n), donde n es el número de elementos de la matriz.

Aplicaciones de la búsqueda binaria

• Búsqueda en bases de datos: Se trata de un algoritmo eficaz para la búsqueda en bases de datos para localizar rápidamente registros basados en campos indexados, como ID o claves.
• Búsqueda de elementos en matrices ordenadas: La búsqueda binaria localiza eficazmente elementos en matrices ordenadas, lo que resulta útil en aplicaciones como la búsqueda de una palabra en un diccionario o la localización de un elemento en una lista ordenada.
• Base algorítmica: Es un componente fundamental en el desarrollo de sofisticados algoritmos de aprendizaje automático. La búsqueda binaria ayuda a entrenar redes neuronales y a optimizar los hiperparámetros del modelo.
• Optimización de algoritmos: La búsqueda binaria se utiliza en algoritmos, incluidas las estrategias de divide y vencerás, para resolver eficazmente problemas como la búsqueda de raíces cuadradas o la localización de elementos máximos en matrices.
• Búsqueda en árboles: Los árboles binarios de búsqueda (BST) utilizan este algoritmo para buscar, insertar y eliminar elementos de forma eficaz manteniendo el orden del árbol.

3. Búsqueda por interpolación

Cuando los valores de una matriz ordenada están distribuidos uniformemente, la búsqueda por interpolación ofrece una ventaja sobre la búsqueda binaria. La interpolación consiste en crear nuevos puntos de datos dentro del espacio de búsqueda conocido.

Mientras que la búsqueda binaria se centra siempre en el elemento central, la búsqueda por interpolación ajusta su posición de búsqueda en función del valor clave buscado. Por ejemplo, si la clave de búsqueda está más cerca del extremo, la búsqueda por interpolación tiende a empezar a buscar desde ese extremo.

Para ponerlo en perspectiva, imaginemos que estás buscando un precio concreto entre una lista de precios de artículos en una tienda. Estos precios están ordenados del más bajo al más alto. En lugar de comprobar siempre la mitad de la lista (como en la búsqueda binaria), la búsqueda por interpolación estima dónde podría estar el precio en función de su valor comparado con los precios más bajos y más altos. A continuación, se repite este proceso hasta encontrar el precio.

El tiempo de ejecución de un algoritmo de búsqueda por interpolación es O(log log n), donde n es el número de elementos de la matriz.

Aplicaciones de la búsqueda por interpolación

• Búsqueda en bases de datos: La búsqueda por interpolación se utiliza habitualmente en bases de datos para buscar registros en función de algún elemento clave.
• Búsqueda en matrices grandes: Este algoritmo de búsqueda facilita una búsqueda más eficiente en grandes matrices ordenadas, especialmente cuando la distribución de valores es uniforme. Puede aplicarse en diversos campos, como la informática científica, donde es necesario buscar de forma eficiente en grandes conjuntos de datos.
• Recuperación de datos de tablas de símbolos: La búsqueda por interpolación puede utilizarse en tablas de símbolos, donde las claves están asociadas a valores. Por ejemplo, en los lenguajes de programación, las tablas de símbolos se utilizan para almacenar variables, funciones y otros identificadores. La búsqueda por interpolación puede localizar rápidamente la información asociada a un identificador específico.
• Aplicaciones sensibles al tiempo: Debido a su capacidad para recuperar datos rápidamente, la búsqueda por interpolación es adecuada para aplicaciones sensibles al tiempo.
• Tablas hash: Eficientes para encontrar datos cuando se combinan con una función hash.

4. Búsqueda por saltos

La búsqueda por saltos, también conocida como búsqueda por bloques, está diseñada específicamente para matrices ordenadas. A diferencia de la búsqueda lineal, que examina cada elemento secuencialmente, la búsqueda por saltos salta en incrementos de tamaño fijo, omitiendo múltiples elementos para realizar búsquedas más rápidas.

Si el elemento objetivo se encuentra dentro de un rango especificado, el algoritmo emplea una búsqueda lineal dentro de ese bloque. Este enfoque reduce sustancialmente las operaciones, mejorando la eficacia de la búsqueda.

Veamos un ejemplo del algoritmo de búsqueda por saltos.

Imagina que intentas encontrar un número concreto en una larga lista de números y quieres hacerlo más rápido que comprobando cada número uno a uno.

1. Decide cuántos números te vas a saltar cada vez que mires: Digamos que saltarás 3 números cada vez.
2. Empieza a buscar en la lista, saltándote la cantidad elegida cada vez, hasta que encuentres un número igual o mayor que el que buscas.
3. Una vez que hayas encontrado un rango donde podría estar el número, realiza una búsqueda lineal hasta que encuentres el objetivo.

El tiempo de ejecución de un algoritmo de búsqueda por saltos es O(√n), donde n es el número de elementos de la matriz ordenada.

Aplicaciones de la búsqueda por saltos

• Aplicaciones JavaScript: La búsqueda por saltos optimiza el proceso de búsqueda en aplicaciones JavaScript, mejorando la eficacia y la capacidad de respuesta.
• Búsqueda en sistemas de bases de datos: Este algoritmo busca registros en función de algún elemento clave en grandes bases de datos.
• Recuperación de datos de medios visuales: La búsqueda por saltos localiza con eficacia un fotograma específico dentro de un archivo de vídeo de gran tamaño avanzando un número fijo de fotogramas cada vez.

5. Búsqueda exponencial

El algoritmo de búsqueda exponencial, también conocido como búsqueda por duplicación o búsqueda galopante, difiere de la búsqueda por saltos en la forma de dividir la matriz y en el tipo de búsqueda empleado dentro de estas divisiones. Mientras que la búsqueda por saltos divide la matriz en bloques y utiliza la búsqueda lineal, la búsqueda exponencial divide la matriz utilizando potencias exponenciales de 2 y aplica la búsqueda binaria.

Básicamente, la función de búsqueda recorre exponencialmente toda la matriz, desde la izquierda, segmentándola en bloques más pequeños utilizando potencias de 2. El algoritmo realiza una búsqueda binaria dentro de cada uno de estos bloques hasta encontrar el objetivo.

Dado que este algoritmo de búsqueda puede ser un poco complejo, vamos a ilustrar su funcionalidad aplicándolo a un escenario de la vida real.

Imagina que tienes una estantería llena de libros ordenados alfabéticamente por título. Estás buscando un libro concreto, digamos “Harry Potter y la piedra filosofal”. En lugar de buscar libro por libro, decides utilizar la búsqueda exponencial.

Así es como funciona:

1. Punto de partida: Empieza por el primer libro de la izquierda de tu estantería. Si este no es el libro que buscas, continúa.
2. Muévete hacia la derecha, duplicando tu ventana de búsqueda: Si encuentras “Harry Potter y la piedra filosofal” en una de estas posiciones, has encontrado tu libro.
3. Repite el proceso: Sigue repitiendo el proceso, duplicando el rango cada vez, hasta que encuentres el libro.

Aunque no es la aplicación exacta de la búsqueda exponencial, este ejemplo ayuda a demostrar cómo se puede localizar rápidamente el libro sin necesidad de ir libro por libro.

El tiempo de ejecución de un algoritmo de búsqueda exponencial es O(log n), donde n es el número de elementos de la matriz ordenada.

Aplicaciones de la búsqueda exponencial

• Búsqueda de datos en grandes matrices ordenadas: La búsqueda exponencial encuentra rápidamente elementos en grandes matrices ordenadas, como listados de productos, ampliando exponencialmente el rango de búsqueda, ideal para situaciones en las que la búsqueda lineal es demasiado lenta.
• Búsqueda en sistemas de archivos: Este algoritmo mejora las búsquedas en sistemas de archivos encontrando rápidamente archivos o directorios dentro de estructuras de directorios mediante la expansión exponencial del rango de búsqueda.

6. Búsqueda ternaria

La búsqueda ternaria es un algoritmo de búsqueda diseñado para determinar la posición de un valor objetivo dentro de una matriz ordenada. A diferencia de la búsqueda binaria, que divide la matriz en dos partes, la búsqueda ternaria la divide en tres. Al comparar el valor objetivo con elementos en dos puntos y dividir la matriz en tres partes, la función de búsqueda reduce eficazmente el espacio de búsqueda.

Para ilustrar un ejemplo, apliquemos la búsqueda ternaria para encontrar el número 6 en la matriz [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Divide el área de búsqueda:
  • Divide tu área de búsqueda en tres partes encontrando dos puntos de división: Un punto está a un tercio de la izquierda (digamos 4), y el otro está a dos tercios de la izquierda (digamos 8).
  • Esto divide el área en [1, 4], (5, 8), y [9, 10].
• Compara con el objetivo:
  • Comprueba si el número que buscamos (6) es igual a 4 o a 8.
  • No es igual a 4 u 8, así que ajusta tus punteros en función de dónde se encuentre el 6.:
    • Como 6 es mayor que 4 pero menor que 8, movemos el puntero izquierdo a 5 y el derecho a 7.
• Repite o concluye:
  • Sigue repitiendo este proceso con el espacio de búsqueda reducido hasta que encuentres el número 6 o no te quede más área de búsqueda.
  • Finalmente, reduces el área de búsqueda a [6, 6], ¡y encuentras el número que buscabas!

El tiempo de ejecución de un algoritmo de búsqueda ternaria es O(log3 n), siendo n el número de elementos de la matriz ordenada.

Aplicaciones de la búsqueda ternaria

• Funciones unimodales: La búsqueda ternaria se aplica en funciones unimodales para identificar sus valores máximos o mínimos. Las funciones unimodales son aquellas que tienen un único valor máximo.

Conclusión

Las aplicaciones de diferentes tipos de algoritmos de búsqueda son vastas y diversas, abarcando desde búsquedas en grandes bases de datos, optimización de aplicaciones, hasta servir como bloques fundamentales para desarrollar algoritmos avanzados de aprendizaje automático para búsquedas.

Teniendo en cuenta las complejidades de tiempo y espacio, capacidades, combinadas con las ventajas y desventajas de cada uno de los algoritmos mencionados, puedes tomar decisiones informadas. Ya sea en tu tarea de clase de informática o cuando estés desarrollando la próxima aplicación revolucionaria, dominando técnicas como búsqueda binaria, DFS, BFS y divide y conquista, puedes desbloquear todo el potencial de las estructuras de datos y mejorar el rendimiento de tu sistema.

Si estás creando o evaluando búsqueda para una tienda en línea específicamente, la mecánica funciona de manera un poco diferente en la práctica. Consulta cómo funciona la búsqueda de comercio electrónico detrás de escenas.

Preguntas frecuentes