Estructura de Datos : Búsqueda Binaria

Definiciones

Las condiciones iniciales son las siguientes :

Los registros del archivo ya están en memoria principal.
Los registros estan almacenados secuencialmente 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 a clasificar.
Todos los registros tienen una clave Ki, donde i es 1 =< i =< n.
Los registros están ordenados respecto de la clave mencionada.
La búsqueda se hará sobre el archivo a partir de una clave que se busca.

La secuencia de acciones es la siguiente :

Se busca por la clave en el registro que esta en la mitad del archivo, donde esta la clave Km.
Se compara la clave que se busca con la clave Km, y se procede de la siguiente manera :
- Si K < Km, se deduce que el registro con clave Km podría estar en la primer mitad del archivo.
- Si K = Km, se halló el registro cuya clave iguala a la de busqueda.
- Si K > Km, se deduce que el registro con clave Km podría estar en la segunda mitad del archivo.
Si K = Km, se da por terminada la búsqueda en forma exitosa.
Si K < Km, se continua la búsqueda, tomando a la primera mitad del archivo, como el subarchivo donde buscar.
Si K > Km, se continua la búsqueda, tomando a la segunda mitad del archivo, como el subarchivo donde buscar.
La búsqueda continua en los dos últimos casos hasta que el subarchivo se reduce a 1 registro.
La última comparación determina si la búsqueda fué exitosa o la clave no existe en el archivo.
Luego de cada comparación el tamaño del subarchivo se reduce en la mitad. Luego de k comparaciones, el subarchivo a procesar tiene, a los sumo, techo de n / ( 2**k ) registros. Deducimos entonces, que en el peor caso, se requieren O(log2 n) comparaciones para buscar en el archivo.

              R1   R2   R3             Rm            Rn-2 Rn-1  Rn
   ........------------------.......--------.......------------------.......
            | K1 | K2 | K3 |         | Km |         |Kn-2|Kn-1| Kn |              n slots
   ........------------------.......--------.......------------------.......

            |<---------------------->|    |<---------------------->|
                 Subarchivo menor              Subarchivo mayor

Funciones

SEQSRCH

Busca en el archivo F, secuencial, con registros R1, R2, ..., Rn y claves K1 =< K2 =< ... =< Kn, por el registro Ri, tal que Ki = K. Si i devuelve 0, no existe un registro en el archivo con la clave buscada. Si i es distinto de 0, es la posición del registro con la clave igual a K. La variable n es la cantidad de registros del archivo. Las variables F, n y K son variables de entrada. La variable i es de salida.

procedure BINSRCH(F,n,i,K)

l <---- 1
u <---- n
while l =< u
- do
  - m <---- piso de ( l + u ) / 2
  - case
    - :K > Km : l <---- m + 1
    - :K = Km : i <---- m; return
    - :K < Km : u <---- m - 1
- end
i <---- 0

end BINSRCH

Veamos ejemplos del c lculo de la posici¢n media. Observar que si n = 6, ( 6 + 1 ) / 2 = 3,5 ----> piso de 3,5 = 3. Observar que si n = 9, ( 9 + 1 ) / 2 = 5 ----> piso de 5 = 5. Observar que si l = u, m = ( l + u ) / 2 = ( 2 * l ) / 2 = l, por lo tanto l = u = m.

Ejemplo K > Km

               R1   R2   R3            Rm-1  Rm  Rm+1           Rn-2 Rn-1  Rn                                           Rm-1  Rm  Rm+1
         ...------------------.......------------------.......------------------.......                        .......------------------.......
             | K1 | K2 | K3 |         |Km-1| Km |Km+1|         |Kn-2|Kn-1| Kn |              n slots                   |Km-1| Km |Km+1|
         ...------------------.......------------------.......------------------.......                        .......------------------.......
                                                                                                                              l ....>
               l                             m    l                         u                                                 u
               .                                  .                                                                           m
               ..................>.................

                                                |<--------------------------->|
                                                 Nuevo subarchivo de busqueda

Ejemplo K < Km


               R1   R2   R3            Rm-1  Rm  Rm+1           Rn-2 Rn-1  Rn                                           Rm-1  Rm  Rm+1
         ...------------------.......------------------.......------------------.......                        .......------------------.......
             | K1 | K2 | K3 |         |Km-1| Km |Km+1|         |Kn-2|Kn-1| Kn |              n slots                   |Km-1| Km |Km+1|
         ...------------------.......------------------.......------------------.......                        .......------------------.......
                                                                                                                              l
               l                         u   m                              u                                            <....u
                                         .                                  .                                                 m
                                         .................<..................

             |<--------------------------->|
              Nuevo subarchivo de busqueda

Observar que cuando el subarchivo se reduce a 1 registro, en la proxima vuelta del while se d que u < l y termina el loop.

Interpretacion usando un arbol binario

Observar que en este algoritmo siempre se usa la clave del registro del medio de un subarchivo como la clave de comparación. Interpretemos la búsqueda binaria como un árbol binario donde el valor de sus nodos es la posición de la clave que se compara. Veamos el siguiente ejemplo :

Archivo con 31 registros, entonces n = 31.

Primer clave comparada, piso de ( 1 + 31 ) / 2, lo que es igual a 16.

Si K < K16, piso de ( 1 + 15 ) / 2, lo que es igual a 8.

Si K > K16, piso de ( 17 + 31 ) / 2, lo que es igual a 24.

...

lo que nos lleva a construir el siguiente árbol binario :

                                              *---*
                                              |1 6|                                                  Primera comparacion
                                              *---*
                                               | |
                        +----------------------+ +----------------------+
                        |                                               |
                      *---*                                           *---*
                      | 8 |                                           |2 4|                          Segunda comparacion
                      *---*                                           *---*
                       | |                                             | |
            +----------+ +----------+                       +----------+ +----------+
            |                       |                       |                       |
          *---*                   *---*                   *---*                   *---*
          | 4 |                   |1 2|                   |2 0|                   |2 8|              Tercera comparacion
          *---*                   *---*                   *---*                   *---*
           | |                     | |                     | |                     | |
      +----+ +----+           +----+ +----+           +----+ +----+           +----+ +----+
      |           |           |           |           |           |           |           |
    *---*       *---*       *---*       *---*       *---*       *---*       *---*       *---*
    | 2 |       | 6 |       |1 0|       |1 4|       |1 8|       |2 2|       |2 6|       |3 0|        Cuarta comparacion
    *---*       *---*       *---*       *---*       *---*       *---*       *---*       *---*
     | |         | |         | |         | |         | |         | |         | |         | |
   +-+ +-+     +-+ +-+     +-+ +-+     +-+ +-+     +-+ +-+     +-+ +-+     +-+ +-+     +-+ +-+
   |     |     |     |     |     |     |     |     |     |     |     |     |     |     |     |
 *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*
 | 1 | | 3 | | 5 | | 7 | | 9 | |1 1| |1 3| |1 5| |1 7| |1 9| |2 1| |2 3| |2 5| |2 7| |2 9| |3 1|     Quinta comparacion ----> u, l y m en la misma posicion
 *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---* *---*

Luego de la quinta comparacion se sale del loop. No hay mas comparaciones. El paso del raíz a cualquier nodo representa la secuencia de nodos recorridos por el algoritmo para encontrar la clave K o determinar que dicha clave no existe en el archivo. Viendo la altura del árbol, se vé que en el peor caso, se hacen no más de O(log2 n) comparaciones. Observar que estan en el arbol todas las posiciones del archivo. Consideremos el siguiente ejemplo, el que busca una clave no existente en el archivo, pero que nos lleva al nodo de la posicion 29.

   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
 |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

   l                                                           m   l                           m   l           m   l   m   u
                                                                                                                   u
                                                                                                                   m