Estructura de Datos : Búsqueda Secuencial

Definiciones

Archivos en memoria principal :

Un archivo ( file ) es un coleccion de registros ( records ).
Un registro tiene uno o mas campos ( fields ).
Un campo es un contenedor de información.
Una clave ( key ) es un campo usado para distinguir a los registros.
Un ejemplo :
- Archivo Guía Telefónica
  - Campo Nombre
  - Campo Dirección
  - Campo Número
- Posibles busquedas
  - Aplicación 1 : Busca por Nombre
  - Aplicación 2 : Busca por Número
  - Aplicación 3 : Busca por Dirección

Las condiciones iniciales son las siguientes :

Los archivos almacenan los registros secuencialmente o no secuencialmente. Utilizaremos la disposición de archivos que almacena los registros secuencialmente. Esto significa que los registros están en posiciones contiguas del almacenamiento.
Los registros del archivo ya estan en memoria principal.
Los registros del archivo los denominaremos R1, R2, R3, ..., Ri, ..., Rn donde 1=< i =< n.
Existen en memoria n slots, donde en cada uno de ellos se dispone un registro del archivo donde se efectuará la búsqueda.
Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.
Los registros pueden estar desordenados respecto de la clave mencionada.
La busqueda se hara sobre el archivo a partir de una clave que se busca.

La secuencia de acciones es la siguiente :

Se agrega al archivo un nuevo registro que ocupa la posición anterior al primer registro del archivo, y que llamaremos R0.
La búsqueda se hace desde el último registro del archivo hacia el primero.
Si la búsqueda es exitosa, lo que significa que la clave que se busca está en el archivo, se retorna la posición del registro que tiene la clave en cuestión.
Si la búsqueda no es exitosa, la búsqueda recorre todo el archivo desde el final del archivo hasta el comienzo del mismo sin hallarla. En virtud de la incorporacion del registro ficticio R0, finalmente la halla. En este caso devuelve un cero, ya que esa es la posición del registro ficticio.

              R1   R2   R3             Ri             Rn
   ........------------------.......--------.......--------.......
            | K1 | K2 | K3 |         | Ki |         | Kn |              n slots
   ........------------------.......--------.......--------.......

         R0   R1   R2   R3             Ri             Rn
   ...-----------------------.......--------.......--------.......
       | K0 | K1 | K2 | K3 |         | Ki |         | Kn |              n + 1 slots
   ...-----------------------.......--------.......--------.......

Funciones

SEQSRCH

Busca en un archivo F, con claves K1, K2, ..., Kn, por el registro Ri, tal que Ki = K. La variable n es la cantidad de registros del archivo. Las variables F, n y K son de entrada. La variable i es de salida e indica la posición del registro hallado, si i es distinto de 0, e indica que no existe un registro con la clave buscada si i es 0.

procedure SEQSRCH(F,n,i,K)

K0 <---- K
i <---- n
while Ki not= K
- do
  - i <---- i - 1
- end

end SEQSRCH


                                               +--.......--+  +-+  +-+  +------ Comenzar
                                               |           |  | |  | |  |
                                               |           |  | |  | |  |
                                               V           |  V |  V |  V
               R0   R1   R2   R3             Ri            Rn-2 Rn-1  Rn
         ...-----------------------.......--------.......------------------.......
             | K0 | K1 | K2 | K3 |         | Ki |         | Kn | Kn | Kn |              n + 1 slots    n - i + 1 comparaciones
         ...-----------------------.......--------.......------------------.......
                                            |
                                            |
                               Existe <-----+

                 +-+  +-+  +-+  +--.......--+  +--.......--+  +-+  +-+  +------ Comenzar
                 | |  | |  | |  |           |  |           |  | |  | |  |
                 | |  | |  | |  |           |  |           |  | |  | |  |
                 V |  V |  V |  V           |  V           |  V |  V |  V
               R0   R1   R2   R3             Ri            Rn-2 Rn-1  Rn
         ...-----------------------.......--------.......------------------.......
             | K0 | K1 | K2 | K3 |         | Ki |         | Kn | Kn | Kn |              n + 1 slots    n - 0 + 1 comparaciones
         ...-----------------------.......--------.......------------------.......
              |
              |
No existe <---+

Observar que el algoritmo siempre encuentra a K, aunque más no sea en el registro ficticio K0, pero en este caso devolvería un i = 0, indicatriz de que realmente no existe un registro con la clave igual a K. Si la clave no existe en el archivo se realizan n + 1 comparaciones. Si la clave existe en el archivo se realizan n - i + 1 comparaciones. El promedio de las búsquedas exitosas es la sumatoria, variando i desde 1 a n, de ( n - i + 1 ), luego dividida la sumatoria por n. La sumatoria anterior es igual a ( n + 1 ) / 2, lo que es igual a 0,5 * n + 0,5. Esto indica que se trata de un algoritmo que responde a un orden de magnitud lineal, del tipo O(n). Observar que si el file estaria ordenado respecto de la clave la búsqueda sería más rapida, ya que podríamos detener la búsqueda ni bien la clave del registro analizado es menor que la que se busca y decretar que no es hallada.

Ejercicios

Implementar la función SEQSRCH1(F,n,i,K), capaz de determinar el registro Ri, del archivo F, de n registros, tal que K sea igual a Ki, en las mismas condiciones que la función SEQSRCH(F,n,i,K), salvo que solo trabaja con archivos ordenados.