 |
| Procedimiento de las búsquedas |
Búsqueda Secuencial
La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial (a veces búsqueda lineal), los elementos de una lista o vector se exploran (se examinan) en secuencia, uno después de otro, La búsqueda secuencial es necesaria, por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfono están organizados alfabéticamente por el nombre del abonado en lugar de por números de teléfono, de modo que deben explorarse todos los números, uno después de otro, esperando encontrar el número 958-2200000.
El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda. Dado que el array no está en un orden prefijado, es probable que el elemento a buscar pueda ser el primer elemento, el último elemento o cualquier otro. De promedio, al menos el programa tendrá que comparar la clave de búsqueda con la mitad de los elementos del array. El método de búsqueda lineal funcionará bien con arrays pequeños o no ordenados. La eficiencia de la búsqueda secuencial es pobre, tiene complejidad lineal, 0(n).
Búsqueda Binaria
La búsqueda secuencial se aplica a cualquier lista. Si la lista está ordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra del primer apellido o de la palabra que busca. Se puede tener suerte y acertar con la página correcta; pero, normalmente, no será así y se mueve el lector a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con "J" y se está en la "L" se mueve uno hacia atrás. El proceso continúa hasta que se encuentra la página buscada o hasta que se descubre que la palabra no está en la lista.
Una idea similar se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de una lista y se comprueba se la clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sigue la búsqueda uno en la mitad inferior o superior del elemento central de la lista. En general, si los datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda.
Comparación de la búsqueda binaria y secuencial
La comparación en tiempo entre los algoritmos de búsquedas secuencial y binaria se va haciendo espectacular a medida que crece el tamaño de la lista de elementos. Tengamos presente que en el caso de la búsqueda secuencial, en el peor de los casos, coincidirá el número de elementos examinados con el número de elementos de la lista tal como representa su complejidad 0(n).
Sin embargo, en el caso de la búsqueda binaria, tengamos presente,por ejemplo, que 2^10=1024, lo cual implica el examen de 11 posibles elementos, si se aumenta el número de elementos de una lista a 2048 y teniendo presente que 2^11=2048 implicará que el número máximo de elementos examinados en la búsqueda binaria es 12. Si se sigue este planteamiento, se puede encontrar el número "m" más pequeño para una lista de 1000000 tal que 2^n >= 1000000. Es decir, 2^19=524288, 2^20=1048576 y por tanto el número de elementos examinados (en el peor de los casos) es 21.
La siguiente tabla muestra la comparación de los métodos de búsqueda secuencial y búsqueda binaria. En la misma tabla se puede apreciar una comparación del número de elementos que se deben examinar utilizando búsquedas secuencial y binaria. Esta tabla muestra la eficiencia de la búsqueda binaria comparada con la búsqueda secuencial y cuyos resultados de tiempo vienen dados por las funciones de complejidad 0(log2 (n)) y 0(n) de las búsquedas binaria y secuencial respectivamente.
 |
| Comparación de las búsquedas binarias y secuencial |
Fuentes:
Comentarios
Publicar un comentario