• Author / Uploaded
• Ian SVm

Citation preview

Instituto Politécnico Nacional

Algoritmo de Búsqueda Secuencial o lineal

Algoritmos Computacionales Unidad Profesional Interdisciplinaria de Ingeniería y Ciencias Sociales y Administrativas “La técnica al servicio de la patria”

• Se utiliza este método cuando los datos almacenados en la estructura de datos (arreglo, matriz, archivo, tabla) no se encuentran ordenados. • Si los datos se encuentran ordenados es más eficiente (rápido) el método de búsqueda binaria.

Búsqueda Secuencial o lineal

• Método de búsqueda secuencial se utiliza para identificar y localizar (buscar) un dato dentro de una estructura de datos.

Un arreglo, vector o lista es una estructura de datos. Al definir la estructura es necesario precisar el número de elementos o casillas que lo conformarán.

int arreglo [5];

En este ejemplo se define un arreglo numérico (permitirá almacenar números) y estará conformado por 5 casillas o elementos

Observe que el arreglo inicia con la casilla CERO

0

1

2

3

4

Apuntador , Puntero o Localidad

Los arreglos o estructura de datos se almacenan en la memoria RAM, por lo tanto al terminar la ejecución del programa se borra el arreglo.

Búsqueda Secuencial o lineal

Arrays, Arreglo, Vector

1.- Crear el arreglo o vector int arreglo [5]; 2.- Capturar los datos en el arreglo for (i=0; ….. cin>>arreglo[i]; Ejemplo:

17 93 12 75 8 0

1

2

3

4

Variable i - Apuntador Indica el numero de casilla en donde se almacenará el dato de entrada Apuntador, Puntero o Localidad

Observe en el ejemplo, que cada dato tecleado se almacena en una casilla independiente en el arreglo.

Búsqueda Secuencial o lineal

Proceso de Búsqueda Secuencial

3.- Se solicita el número a buscar dentro del arreglo

cin>>numero; Ejemplo:

numero 75

arreglo 17 93 12 75 8 0

1

2

3

4

Apuntadores, Punteros o localidades

Observe que el dato a buscar es el numero 75

Búsqueda Secuencial o lineal

Proceso de Búsqueda Secuencial

17 93 12 75 8 0

¿Son iguales?

4.-

1

75

2

3

4

Apuntadores, Punteros o localidad

numero

Se efectúa una comparación del número a buscar con cada uno de los elementos contenidos en el arreglo. Se pregunta si son iguales: o Son iguales – Se dice que se encontró el numero dentro del arreglo y se termina el proceso. o No son iguales – Se sigue el proceso de comparación. Si se han terminado los elementos del arreglo a comparar, se dice que no se encuentra el número buscado en el arreglo y se termina el proceso.

Búsqueda Secuencial o lineal

Proceso de Búsqueda Secuencial

Ejemplo:

arreglo 17 93 12 75 8 0

1

2

3

4

En la cuarta comparación encuentra el elemento dentro del arreglo y termina el proceso de comparación

Este método localiza el dato aunque los números se encuentren desordenados en el vector

Búsqueda Secuencial o lineal

numero 75

Existe el dato en el arreglo

Ejemplo:

arreglo 17 93 12 75 8 0

1

2

3

4

Compara el numero buscado contra todos los elementos

Efectúa toda la comparación pero si no encuentra el numero dentro del arreglo, se debe enviar un mensaje de error.

Búsqueda Secuencial o lineal

numero 79

NO existe el dato en el arreglo

17 93 12 75 8 0

1

8

2

3

4

Búsqueda Secuencial o lineal

El peor de los casos Apuntadores, Punteros o localidad

numero

En el peor de los casos el número buscado se encuentra al final del arreglo, por lo tanto se realizarán tantas comparaciones como el tamaño de la estructura (arreglo, matriz, archivo) tenga. Esto se vuelve un problema si el tamaño de la estructura es de cientos o miles de datos. 9

El peor de los casos 17 93 12 75 8 0

1

17

2

3

4

Apuntadores, Punteros o localidad

numero

En el mejor de los casos el numero buscado se encuentra al principio, por lo tanto solamente se realizará una comparación.

10

#include "iostream.h"

// Busqueda Lineal main() { int arreglo [5], i=0, x=0, numero=0, encontrado=0; // Captura la datos en el arreglo cout