Búsqueda secuencial en tabla ordenada

1

Búsqueda secuencial en tabla ordenada.

Estructura de datos

Estructura de datos

2 Búsqueda secuencial

La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en

recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). . La

búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún

registro con esa llave. Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas.

Estructura de datos

3

Si el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.

Estructura de datos

4

Búsqueda secuencial

Ejemplo: Vectores no ordenados

5

Llenar un vector de 9 datos

1 2 3 4 5 6 7 8 9

Dato encontrado en las posiciones

Dato a buscar

Llave N =

0 1 2 3 4 5 6 7 83 5 18 3 5 16 4 22 5

5

1 2 3 4 5 6 7 83 5 18 3 5 16 4 22 5

Estructura de datos

Estructura de datos

6Búsqueda secuencial Lineal

Ejemplo: Tabla no ordenada

7 40534 Mauricio Villalobos 7 8 8

Código Nombre Dirección Notas

1 2 3

98034 Lorena Castillo 10 7 8

12590 Carlos Orellana 6 5 9

45633 Karla Pérez 5 10 10

22349 Julio Martínez 7 7 8

Dato a buscar

Mauricio Villalobos 7 8 8

Lorena Castillo 10 7 8

Carlos Orellana 6 5 9

Karla 5 10 10

Julio Martínez 7 7 8

=45633

40534

98034

12590

22349

45633 Pérez

Dato encontrado

Estructura de datos

Estructura de datos

8 Desventaja de búsqueda secuencial lineal.

El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

Este método de búsqueda es muy lento, pero si los datos no están en orden, es el único método que puede emplearse para hacer las búsquedas. Para poder agilizar la búsqueda en arreglos se implementan las siguientes mejoras:

Estructura de datos

9 Mejoras en la eficiencia de la búsqueda secuencial

Muestreo de acceso: Este método consiste en

observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas

Movimiento hacia el frente:

Este esquema consiste en que la lista de registros se reorganice dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que él.

Estructura de datos

10

Transposición:

Consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros..

Ordenamiento: Ordenar los registros en base al

valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

Estructura de datos

11 Búsqueda en tabla ordenada.

Los métodos de búsquedas presentan un inconveniente, cuando no se encuentra el elemento buscado, pues el recorrido en tablas de mayor

tamaño consume más tiempo, para ello, un método simple consiste en colocar los elementos dentro de la tabla de acuerdo con algún orden sobre sus llaves, de esta manera, cuando se busca un elemento, es posible identificar la posición que debería ocupar la llave, y si no se

localiza en ella, es porque no se encuentra en la tabla.

El ordenamiento de las llaves exige que, dados los valores de dos llaves y , se cumplan una y solo una de las siguientes condiciones (Propiedad

de tricotomía sobre los valores de las llaves ):

la ley de tricotomía es una propiedad de algunos conjuntos ordenados, por la cual todos sus elementos son comparables entre sí.

Estructura de datos

12 Búsqueda exhaustiva

Se puede recorrer la tabla desde uno de sus extremos, hasta encontrar la posición en que debería estar la llave buscada, de acuerdo al orden que mantenga la tabla.

13 1234 Mauricio Villalobos 7 8 8

Código Nombre Dirección Notas

1 2 3

1422 Lorena Castillo 10 7 8

3245 Carlos Orellana 6 5 9

4567 Karla Pérez 5 10 10

4606 Julio Martínez 7 7 8

Dato a buscar

Mauricio Villalobos 7 8 8

Lorena Castillo 10 7 8

Carlos Orellana 6 5 9

Karla 5 10 10

Julio Martínez 7 7 8

=3245

1234

1422

3245

4606

4567 Pérez

Dato encontrado

Estructura de datos

1

2

3

5

4

Posición

3

14 Búsqueda con centinela en tablas ordenadas.

Una vez más, se puede eliminar la condición compuesta de control del ciclo, colocando la llave buscada en uno de los extremos de la tabla, que no se utilice normalmente para almacenar los datos.

Estructura de datos

Luego se compara si el índice retornado corresponde al valor buscado.

Estructura de datos

15

Búsqueda Secuencial Indexada

Estructura de datos

16 Búsqueda Secuencial Indexada

Registros

Un archivo es un conjunto de datos en una colección de registros, que constan de diferentes entidades de nivel más bajo denominadas campos.


Estructura de datos

Registros Un registro es una colección de campos lógicamente relacionados un

ejemplo puede ser la información de un libro que contiene los campos de título, autor, editorial, fecha de edición, entre otros.


Estructura de datos

Campo clave Una clave es un campo que identifica al registro y lo diferencia de otros

registros. Normalmente los registros se organizan según un campo clave.

Ej. son números de identificación, nombres; en general puede ser una clave de cualquier campo que admita relaciones de comparación.


Estructura de datos

Partes del Archivo S.I.

La clave se asocia con la dirección (posición) del registro de datos en el archivo principal.

Área de datos. Contiene los registros de datos en forma secuencial, sin dejar huecos intercalados.

Área de índices. Es una tabla que contiene la clave identificativa y la dirección de almacenamiento.


Estructura de datos

Indice Es una referencia que nos permite obtener de forma automática la

ubicación de la zona del archivo físico donde se encuentra el registro buscado. Este permite localizar un registro por medio de su clave sin recorrer previamente todos los que le preceden.

Cada archivo S.I. consta de dos archivos el de índices y el de datos, el primero es secuencial y contiene las claves del último registro de cada bloque físico del archivo y la dirección de acceso al primer registro del bloque y en el segundo, los registros de datos, clasificados en orden ascendente por el campo clave.


Estructura de datos


Estructura de datos

Ventajas Importantes

Rápido acceso, y que la gestión de archivos se encarga de relacionar la posición de cada registro con su contenido mediante la tabla de índices.

Inconveniente

Es el espacio adicional para guardar el área de índices.

23

Integrantes

Estructura de datosESTRUCTURA DE DATOS NOV -2013

Chavarría Segovia, Edwin Geovanny

Hernández Álvarez, José Nehemías

Jiménez Álvarez, Jackeline Elizabeth

Membreño Cañas, Eduardo Leonel

Romero, Lucio Alberto

Technology

Búsqueda secuencial en tabla ordenada