Métodos de Búsqueda

El método de búsqueda secuencial consiste en revisar la estructura de datos elemento por elemento hasta encontrar el dato que estamos buscando, o hasta llegar al final de la estructura de datos.

Normalmente cuando una función de búsqueda concluye con éxito, lo que interesa es conocer en qué posición fue encontrado el elemento buscado.

La búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o desordenadas.

Si se aplica a una estructura desordenada y el elemento que se está buscando existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta  que se llegue al fin de la estructura.

Ejemplo. Si tenemos una estructura con los elementos 5, 8, 3, 2, 9, 5, 7, 0, 5, 1 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría las posiciones 0, 5 y 8 y el proceso terminaría al llegar al numero 1 que es el ultimo de la lista de elementos.

Ejercicio. Crear un programa que aplique una búsqueda secuencial de un dato dentro de un arreglo de elementos desordenados y presenta la o las posiciones donde encontró el dato.

En cambio con una estructura ordenada al encontrar el elemento por primera vez podemos suponer que una vez que el elemento ya no sea igual al que estamos buscando, ya no es necesario llegar hasta el fin de la estructura.

Ejemplo. Si tenemos la estructura anterior pero ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el mismo número 5, el resultado de la búsqueda nos mostraría las posiciones  4, 5, y 6, y el proceso terminaría ya que el número 7 no es menor ni igual al que estamos buscando.

Ejercicio para reflexionar. Crear un programa que aplique una búsqueda secuencial de un dato dentro de un arreglo de elementos ordenados y presenta la o las posiciones donde encontró el dato.

Por ejemplo dado el siguiente arreglo:

• Si busco el 15, consulto todos los elementos hasta encontrarlo y averiguando así posición en la que se encuentra.

• Si busco el 20, se revisan todos los elementos y al final debería recibir un mensaje que indique que dicho elemento no se encuentra.

Lo bueno de la búsqueda secuencial es que no requiere que el conjunto esté previamente ordenado, pero como debe revisar todos los elementos se torna muy lenta.

A continuación se muestra el diagrama de flujo de Búsqueda Binaria suponiendo que buscamos el valor T dentro del arreglo X[ ]:

A continuación se muestra un fragmento de código en C correspondiente al diagrama de flujo anterior:

int i;
float X[N];
float valor;
int Encontrado;
.
i = 0;
Encontrado = 0;

while (Encontrado == 0 && i < N)
  {
if (X[i]==valor) Encontrado = 1;
else i++;
  }

if(Encontrado==1) printf("El valor se encuentra en la posicion %i",i);
else printf("El valor no se encuentra");