Uniform binary search

Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth's "The Art of Computer Programming". It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth's MIX) on which

*a table lookup is generally faster than an addition and a shift, and
*many searches will be performed on the same array, or on several arrays of the same length

C implementation

The uniform binary search algorithm looks like this, when implemented in C.

#define LOG_N 42 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 ", i, unisearch(a, i)); return 0; }

References

*Knuth. "The Art of Computer Programming", Volume 3. Page 412, Algorithm C.

External links

* [http://huizen.dto.tudelft.nl/deBruijn/knuth/unizoek.pas An implementation of Knuth's algorithm] in Pascal, by Han de Bruijn