Algoritmos de Búsqueda

 

Los algoritmos de búsqueda tiene la finalidad de encontrar un dato, valor u objeto dentro de una estructura de datos o arreglo.

Se han desarrollado un conjunto de algoritmos de búsqueda que varían en complejidad, eficiencia y tamaño del dominio de búsqueda.

Si se conoce por anticipado en qué tipo de “orden” inicial se encuentran los datos, es posible elegir de manera más factible y sencilla el tipo de algoritmo adecuado para encontrar el dato o valor que se desea obtener.

Entre los algoritmos de búsqueda podemos mencionar algunos tales como:

Búsqueda Secuencial o Lineal.

 

La búsqueda secuencial o lineal probablemente es sencilla de implementar e intuitiva.

Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado.

Realiza la comparación de cada elemento, comenzando desde la izquierda.

 

Búsqueda Binaria.

 

 

Para utilizar este algoritmo, el arreglo debe estar ordenado. La búsqueda binaria consiste en dividir el arreglo por su elemento medio en dos sub arreglos más pequeños, despues se procede a comparar el elemento buscado con el del centro. Si los elementos coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer sub arreglo, y si es mayor está en el segundo.

 

Hashing (Dispersión).

 

 

La funcion hashing de dispersion es basicamente una caja negra que tiene como entrada una llave y como salida una dirección.

Consiste en convertir el elemento almacenado en una dirección dentro del array.

 

Búsqueda en Texto (KMP).

 

 

Este algoritmo, consiste en utilizar heurísticas (trata de métodos exploratorios durante la resolución de problemas) para reducir el número de comparaciones entre caracteres realizadas durante la búsqueda.

Pertenece a la familia de algoritmos Morris-Pratt. Mejora el algoritmo de fuerza bruta, tratando de evitar comparaciones ya hechas en una iteración anterior. Al igual que fuerza bruta, puede buscar cadenas de cualquier longitud, por lo que lo podríamos utilizar para encontrar frases extensas.

x: patrón buscado.
y: texto de búsqueda.

 

Hashing (Función Cuadrática).

 

 

Eleva al cuadrado la llave y toma los digitos centrales como direccion, el numero de digitos a tomar queda determinado por el rango del indice.