Jednotné binární vyhledávání - Uniform binary search
Jednotné binární vyhledávání je optimalizace klasiky binární vyhledávání algoritmus vynalezl Donald Knuth a uveden v Knuthově Umění počítačového programování. Používá a vyhledávací tabulka aktualizovat index jednoho pole, spíše než brát střed horní a dolní meze při každé iteraci; proto je optimalizován pro architektury (například Knuth's SMĚS ) na kterých
- vyhledávání v tabulce je obecně rychlejší než přidání a posun a
- mnoho vyhledávání bude provedeno na stejném poli nebo na několika polích stejné délky
C implementace
Uniformu binární vyhledávací algoritmus vypadá takto, když je implementován v C.
#define LOG_N 4statický int delta[LOG_N];prázdnota make_delta(int N){ int Napájení = 1; int i = 0; dělat { int polovina = Napájení; Napájení <<= 1; delta[i] = (N + polovina) / Napájení; } zatímco (delta[i++] != 0);}int neobjevit(int *A, int klíč){ int i = delta[0] - 1; / * střed pole * / int d = 0; zatímco (1) { -li (klíč == A[i]) { vrátit se i; } jiný -li (delta[d] == 0) { vrátit se -1; } jiný { -li (klíč < A[i]) { i -= delta[++d]; } jiný { i += delta[++d]; } } }}/ * Příklad použití: * /# definovat N 10int hlavní(prázdnota){ int A[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19}; make_delta(N); pro (int i = 0; i < 20; ++i) printf("% d je na indexu% d", i, neobjevit(A, i)); vrátit se 0;}
Reference
- Knuth. Umění počítačového programování, Svazek 3. Strana 412, Algoritmus C.
externí odkazy
- Implementace Knuthova algoritmu v Pascal od Han de Bruijn
- Implementace Knuthova algoritmu v Jít tím, že Adrianus Warmenhoven