busca binária uniforme - Uniform binary search
Busca binária uniforme é uma otimização do clássico de busca binária algoritmo inventado por Donald Knuth e prestadas de Knuth The Art of Computer Programming . Ele usa uma tabela de pesquisa para actualizar um único índice de matriz, em vez de tomar o ponto médio de um limite superior e um limite inferior de cada iteração; Portanto, é optimizada para arquitecturas (tais como de Knuth MIX ) no qual
- uma pesquisa da tabela é geralmente mais rapidamente do que uma adição e uma mudança, e
- muitas pesquisas irão ser realizada na mesma matriz, ou em várias matrizes do mesmo comprimento
implementação C
O uniforme algoritmo de busca binária parece com isso, quando implementados em 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 i, a[N] = {1,3,5,6,7,9,14,15,17,19}; make_delta(N); for (i=0; i < 20; ++i) printf("%d is at index %d\n", i, unisearch(a, i)); return 0; }
Referências
- Knuth . The Art of Computer Programming , Volume 3. Page 412, Algoritmo C.
links externos
- Uma implementação do algoritmo de Knuth em Pascal , por Han de Bruijn
- Uma implementação do algoritmo de Knuth em Go , por Adrianus Warmenhoven