Búsqueda binaria uniforme - Uniform binary search
La 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 único índice de matriz, 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 Knuth's MIX ) en las que
- una búsqueda de tabla es generalmente más rápida que una adición y un cambio, y
- muchas búsquedas se realizarán en la misma matriz o en varias matrices de la misma longitud
Implementación de C
Los uniformes binarios algoritmo de búsqueda es similar al siguiente, cuando se implementa en C .
#define LOG_N 4
static int delta[LOG_N];
void make_delta(int N)
{
int power = 1;
int i = 0;
do {
int half = power;
power <<= 1;
delta[i] = (N + half) / power;
} while (delta[i++] != 0);
}
int unisearch(int *a, int key)
{
int i = delta[0] - 1; /* midpoint of array */
int d = 0;
while (1) {
if (key == a[i]) {
return i;
} else if (delta[d] == 0) {
return -1;
} else {
if (key < a[i]) {
i -= delta[++d];
} else {
i += delta[++d];
}
}
}
}
/* Example of use: */
#define N 10
int main(void)
{
int a[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};
make_delta(N);
for (int i = 0; i < 20; ++i)
printf("%d is at index %d\n", i, unisearch(a, i));
return 0;
}
Referencias
- Knuth . El arte de la programación de computadoras , Volumen 3. Página 412, Algoritmo C.
enlaces externos
- Una implementación del algoritmo de Knuth en Pascal , por Han de Bruijn
- Una implementación del algoritmo de Knuth en Go , por Adrianus Warmenhoven