Algoritmos de Búsqueda

Los algoritmos de búsqueda son aquellos destinados a ubicar un valor determinado dentro de un conjunto de datos, como por ejemplo un número dentro de un vector.

Búsqueda Secuencial (lineal): Se utiliza en vectores no ordenados. El dato que se requiere buscar, se va comparando uno por uno (secuencialmente) con los contenidos en el vector hasta encontrarlo, o en caso contrario, recorrerlo por completo.

Se tiene que en un vector con «n» elementos:
Mejor caso: 1 comparación.
Caso promedio: n/2 comparaciones.
Peor caso: n comparaciones.

Búsqueda Binaria: Se utiliza sólamente cuando el vector está ordenado. Para ello, se selecciona un elemento cualquiera del vector, preferentemete central, y se compara con el elemento a buscar; si el valor tomado es mayor, se continúa realizando el procedimiento por la sección a la izquierda de éste ignorando la otra parte; si es menor se procede con la sección a la derecha hasta encontrar el valor o, en el peor de los casos, no encontrarlo.

Se tiene que en un vector con «n» elementos:
Mejor caso: 1 comparación.
Caso promedio: 1/2 log₂n comparaciones.
Peor caso: log₂n comparaciones.

Búsqueda Hash: Se utiliza en elementos que se encuentren ordenados. A cada elemento se le asigna un índice, generalmente en un arreglo (array), que son obtenidos mediante la transformación de estos elementos en un número, mediante las funciones de Hashing (transformación de claves). Entre ellas:

– Plegamiento: Se divide la clave en partes iguales (con excepción de la última que puede ser menor) y se aplica una operación aritmética sobre ellos para determinar el índice dentro del arreglo. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de 1000 elementos, se divide en cifras de 2, 2 y 3 y luego se suman para obtener el índice:

5700931 »> 57 + 00 + 931 »> 988

– Truncamiento: Considera sólo una parte de la clave y la toma como índice dentro del vector, ingorando el resto. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de 1000 elementos, se pueden tomar el segundo, el cuarto y el sexto para formar un nuevo número:

5700931 »> 703

– Aritmética Modular: Se toma la clave y se divide por el largo del vector, obteniendo el resto de esa operación para utilizarla como índice.

– Mitad del Cuadrado: Se calcula el cuadrado del número y luego se utilizan las cifras centrales de aquel cálculo para determinar el índice dentro del arreglo. Por ejemplo, para un arreglo de 100 elementos:

5793 »> 33558849 »> 58