Hispanopedia WikiLa búsqueda binaria uniforme es una optimización del algoritmo de búsqueda binaria clásico inventado por Donald Knuth y presentado en The Art of Computer Programming de Knuth . Utiliza una tabla de búsqueda para actualizar un índice de matriz único, en lugar de tomar el punto medio de un límite superior e inferior en cada iteración; por lo tanto, está optimizado para arquitecturas (como MIX de Knuth ) en las que
- Una búsqueda en una tabla es generalmente más rápida que una adición y un desplazamiento, y
- Se realizarán muchas búsquedas en la misma matriz o en varias matrices de la misma longitud.
Implementación en C
El algoritmo de búsqueda binaria uniforme se ve así, cuando se implementa en C.
#define LOG_N 4
int estático delta [ LOG_N ];
void make_delta ( int N ) { int potencia = 1 ; int i = 0 ;
hacer { int mitad = potencia ; potencia <<= 1 ; delta [ i ] = ( N + mitad ) / potencia ; } mientras ( delta [ i ++ ] != 0 ); }
int unisearch ( int * a , int key ) { int i = delta [ 0 ] - 1 ; /* punto medio de la matriz */ int d = 0 ;
mientras ( 1 ) { si ( clave == a [ i ]) { devuelve i ; } de lo contrario si ( delta [ d ] == 0 ) { devuelve -1 ; } de lo contrario { si ( clave < a [ i ]) { i -= delta [ ++ d ]; } de lo contrario { i += delta [ ++ d ]; } } } }
/* Ejemplo de uso: */
#define N 10
int principal ( void ) { int a [ N ] = { 1 , 3 , 5 , 6 , 7 , 9 , 14 , 15 , 17 , 19 };
hacer_delta ( N );
para ( int i = 0 ; i < 20 ; ++ i ) printf ( "%d está en el índice %d \n " , i , unisearch ( a , i ));
devuelve 0 ; }
Referencias
- Knuth . El arte de la programación informática , volumen 3. Página 412, Algoritmo C.
