Bsqueda secuencial
La bsqueda secuencial busca un elemento de una lista utilizando un valor
destino llamado clave. En una bsqueda secuencial (a veces llamada bsqueda
lineal), los elementos de una lista o vector se exploran (se examinan) en
secuencia, uno despus de otro. La bsqueda secuencial es necesaria, por
ejemplo, si se desea encontrar la persona cuyo nmero de telfono es 958220000 en un directo- rio o listado telefnico de su ciudad. Los directorios de
telfonos estn organizados alfabticamente por el nombre del abonado en
lugar de por nmeros de telfono, de modo que deben explorarse todos los
nmeros, uno despus de otro, esperando encontrar el nmero 958-220000.
El algoritmo de bsqueda secuencial compara cada elemento del array con la
clave de bsque- da. 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 bsqueda con la mitad de los elementos del array. El
mtodo de bsqueda lineal funcionar bien con arrays pequeos o no
ordenados. La eficiencia de la bsqueda secuencial es pobre, tiene complejidad
lineal, O(n).
Complejidad de la bsqueda secuencial
La complejidad de la bsqueda secuencial diferencia entre el comportamiento
en el caso peor y mejor. El mejor caso se encuentra cuando aparece una
coincidencia en el primer elemento de la lista y en ese caso el tiempo de
ejecucin es O(1). El caso peor se produce cuando el elemento no est en la
lista o se encuentra al final de la lista. Esto requiere buscar en todos los n
trminos, lo que implica una complejidad de O(n).
El caso medio requiere un poco de razonamiento probabilista. Para el caso de
una lista aleatoria es probable que una coincidencia ocurra en cualquier
posicin. Despus de la ejecucin de un nmero grande de bsquedas, la
posicin media para una coincidencia es el elemento central n/2. El elemento
central ocurre despus de n/2 comparaciones, que define el coste esperado de
la bsqueda. Por esta razn, se dice que la prestacin media de la bsqueda
secuencial es O(n).
Comparacin de la bsqueda binaria y secuencial
La comparacin en tiempo entre los algoritmos de bsqueda secuencial y
binaria se va haciendo espectacular a medida que crece el tamao de la lista
de elementos. Tengamos presente que en el caso de la bsqueda secuencial,
en el peor de los casos, coincidir el nmero de elementos examina- dos con el
nmero de elementos de la lista tal como representa su complejidad O(n).
Sin embargo, en el caso de la bsqueda binaria, tengamos presente, por
ejemplo, que 210 = 1.024, lo cual implica el examen de 11 posibles
elementos; si se aumenta el nmero de elementos de una lista a 2.048 y
teniendo presente que 211 = 2.048 implicar que el nmero mximo de
elementos examinados en la bsqueda binaria es 12. Si se sigue este
planteamiento, se puede encontrar el nmero m ms pequeo para una lista
de 1.000.000, tal que
2n 1.000.000
Es decir, 219 = 524.288, 220 = 1.048.576 y por tanto el nmero de
elementos examinados (en el peor de los casos) es 21.
La Tabla 6.2 muestra la comparacin de los mtodos de bsqueda secuencial y
bsqueda binaria. En la misma tabla se puede apreciar una comparacin del
nmero de elementos que se deben examinar utilizando bsquedas secuencial
y binaria. Esta tabla muestra la eficiencia de la bsqueda binaria comparada
con la bsqueda secuencial y cuyos resultados de tiempo vienen dados por las
funciones de complejidad O(log2 n) y O(n) de las bsquedas binaria y
secuencial respectivamente.
Tabla 6.2. Comparacin de las bsquedas binaria y secuencial
Nmeros de elementos examinados
Tamao de la lista Bsqueda binaria Bsqueda secuencial
1
10
10
1.000
11
1.000
5.000
14
5.000
100.000
18
100.000
1.000.000
21
1.000.000
A Tener en cuenta
La bsqueda secuencial se aplica para localizar una clave en un vector no
ordenado. Para aplicar el algoritmo de bsqueda binaria la lista, o vector,
donde se busca debe de estar ordenado.
La complejidad de la bsqueda binaria es logartmica, O(log n), ms eficiente
que la bsqueda secuencial que tiene complejidad lineal, O(n).
Algoritmo de bsqueda
Para otros usos de este trmino, vase Bsqueda.
Un algoritmo de bsqueda es aquel que est diseado para localizar un
elemento con ciertas propiedades dentro de una estructura de datos; por
ejemplo, ubicar el registro correspondiente a cierta persona en una base de
datos, o el mejor movimiento en una partida de ajedrez.
La variante ms simple del problema es la bsqueda de un nmero en un
vector.
Mtodo de Bsqueda Secuencial:
Este mtodo se usa para buscar un elemento de un vector, es explorar
secuencialmente el vector, es decir; recorrer el vector desde el prior elemento
hasta el ltimo. Si se encuentra el elemento buscado se debe visualizar un
mensaje similar a Fin de Bsqueda o Elemento encontrado y otro que diga
posicin= en caso contrario, visualizar un mensaje similar a Elemento no
existe en la Lista.
Este tipo de bsqueda compara cada elemento del vector con el valor a
encontrar hasta que este se consiga o se termine de leer el vector completo.
Mtodo de Bsqueda Binaria:
Es un mtodo que se basa en la divisin sucesiva del espacio ocupado por el
vector en sucesivas mitades, hasta encontrar el elemento buscado.
Esta bsqueda utiliza un mtodo de divide y vencers para localizar el valor
deseado. Con este mtodo se examina primero el elemento central de la lista;
si este es el elemento buscado entonces la bsqueda ha terminado. En caso
contrario se determina si el elemento buscado est en la primera o segunda
mitad de la lista y a continuacin se repite el proceso anterior, utilizando el
elemento central de esta sublista. Este tipo de bsqueda se utiliza en vectores
ordenados.
DIFERENCIAS ENTRE METODOS DE BUSQUEDA SECUENCIAL Y BINARIA
El mtodo secuencial y el mtodo binario se diferencian porque el mtodo
secuencial realiza una bsqueda casilla por casilla y comparndolas con el
valor que se desea, y el mtodo binario realiza una bsqueda directa en el
centro del arreglo y la compara con el valor deseado.
En el caso del mtodo de bsqueda binaria, los arreglos deben estar
nicamente ordenados, como se planteo anteriormente, por su parte el mtodo
de bsqueda secuencial o lineal, puede emplearse tanto en arreglos pequeos,
como en aquellos que no estn ordenados.
En segundo orden, podemos ver que el mtodo de bsqueda binaria, es el
mtodo ms eficiente para encontrar elementos en un arreglo ordenado, lo
contrario sucede con el mtodo de bsqueda secuencial ya que este es muy
lento, pero si los datos no estn en orden es el nico mtodo que puede
emplearse para hacer las bsquedas.
Ventajas.
1. Es eficiente cuando un arreglo no esta ordenado es la nica manera en la
que se puede emplear.
Desventajas.
1. Es muy lento.
2. Requiere mucho tiempo, debido a que se comparan uno a uno.
