Búsqueda Secuencial

Teoría

La búsqueda secuencial es un algoritmo de búsqueda donde se evalúan los elementos uno por uno hasta llegar con el que se está buscando o en su defecto hasta llegar al final.
Se usa en conjuntos que no están ordenados, algo que hay que destacar es que como se compara con todos los elementos, no se puede saber si un elemento está en el conjunto hasta evaluar todos.

Caso de estudio

Ud. está en una fiesta y alguien le pide el favor de llevar una bebida a un invitado que Ud. no conoce, los invitados están recostados contra la pared en forma de fila y el único dato que le dan es el nombre: “Alejandra”.

La idea es preguntarles a todos hasta llegar con la persona que se está buscando.

-¿Sujeto 1 Ud. se llama “Alejandra”?
-No, pero la vi por ahí.

-¿Sujeto 2 Ud. se llama “Alejandra”?
-No, ¡yo soy hombre que le pasa!

-¿Sujeto 3 Ud. se llama “Alejandra”?
-Sí, esa bebida es para mí gracias.

En este caso solo le preguntamos a 3 personas, pero se puede dar el caso que la primera persona a la que le preguntemos sea la que estamos buscando, así como que sea la última o simplemente que no esté pero para eso hay que verificar todos los elementos.

Algoritmo

Se identificó el siguiente algoritmo teniendo en cuenta el caso de estudio:

1. Verificar el primer elemento de la lista
a. El elemento coincide con el que estamos buscado (fin).
b. El elemento NO coincide con el que estamos buscado, se continúa con el paso 2.
2. Se continúa con el siguiente elemento, vuelve al paso 1 pero teniendo como primer elemento de la lista este elemento (este paso se repite hasta que no existan elementos en la lista en este caso el elemento no está en la lista).

Búsqueda binaria

Teoria

Este algoritmo se usa para buscar elementos en un conjunto de datos ordenados tipo lista.

La idea es la siguiente, usando el principio divide y vencerás ir limitando el rango de búsqueda, como cuando se busca una página de un libro, se abre el libro en una página al azar, si está más adelante pues pasamos un grupo de páginas así delante de lo contrario nos devolvemos, reduciendo el rango de búsqueda hasta llegar a la página buscada.
Se compara el elemento a buscar, con un elemento central de la lista, si este elemento central es mayor que el del elemento buscado, se toma el intervalo inferior (del inicio a la mitad de la lista, en caso contrario se toma la parte de superior (que va desde el elemento de la mitad hasta el final); en los dos casos, se repite el procedimiento en la parte del lista seleccionada. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en toda la lista.

Caso estudio

Buscando en su ordenada colección de comics Alexander que hallar la edición 84 de “The Walking Dead”, lo haría de la siguiente manera.

1. Se divide la lista en dos y se ubica el elemento de la mitad, en este caso TWD 77.

2. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (77) es menor, entonces se toma la parte “superior” de la lista.

3. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

4. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (99) es mayor, entonces se toma la parte “inferior” de la lista.

5. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

6. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (84) es mayor, como son igual quiere decir que ya encontramos el elemento que estábamos buscando y está en la posición 7.

Algoritmo

1. Se busca el elemento de la mitad de la lista.
2. Se compara con el elemento que se está buscando.
a. Si el elemento de la mitad es mayor, se toma la parte de inferior de la lista (del primer elemento al de la mitad) vuelve al paso 1 pero con esta nueva sublista.
b. Si el elemento de la mitad es menor, se toma la parte de superior de la lista (del elemento de la mitad hay último elemento) vuelve al paso 1 pero con esta nueva sublista.
c. Si el elemento de la mitad es igual al elemento que estamos buscando se concluye la búsqueda exitosamente (fin).
d. Es el último elemento de la lista y no es igual al que se está buscando, el elemento no está en la lista (fin).