Entendiendo los Distintos Tipos de Algoritmos de Búsqueda

Los algoritmos de búsqueda son como detectives digitales que te ayudan a encontrar lo que buscas en grandes colecciones de datos. Varios tipos de algoritmos de búsqueda utilizan reglas y procesos sistemáticos para clasificar grandes conjuntos de información, como sitios web o bases de datos, con el menor número posible de comparaciones o iteraciones para encontrar los elementos de búsqueda deseados.

Los algoritmos de búsqueda desempeñan un papel vital en las interacciones digitales de la vida cotidiana. Desde motores de búsqueda como Google hasta plataformas de e-commerce como Amazon, pasando por redes sociales como Facebook y servicios de streaming como Netflix, estos algoritmos son herramientas esenciales para cribar eficientemente enormes cantidades de datos y ofrecer resultados relevantes.

Entender los pasos básicos y las aplicaciones de un algoritmo de búsqueda es esencial para comprender cómo funcionan y cumplir su objetivo con eficacia. En este artículo, conocerás los algoritmos de búsqueda más comunes, sus complejidades temporales, cómo funcionan sus procesos de búsqueda y sus aplicaciones en la vida real.

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.

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 los algoritmos de búsqueda son amplias y diversas, desde la búsqueda en grandes bases de datos y la optimización de aplicaciones hasta la creación de algoritmos avanzados de aprendizaje automático.

Si tienes en cuenta las complejidades temporales, las capacidades, combinadas con las ventajas y desventajas de cada uno de los algoritmos mencionados, podrás tomar decisiones informadas. Ya sea en la clase de informática o a la hora de desarrollar la próxima app revolucionaria.

Preguntas frecuentes