Uniform binary search explained

Uniform binary search is an optimization of the classic binary search algorithm. It was first published by Donald Knuth, in The Art of Computer Programming, who credited its idea to Ashok K. Chandra.^[1] 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.

1. define LOG_N 4

static int delta[LOG_N];

void make_delta(int N)

int unisearch(int *a, int key)

/* Example of use: */

1. define N 10

int main(void)

References

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

External links

• An implementation of Knuth's algorithm in Pascal, by Han de Bruijn
• An implementation of Knuth's algorithm in Go, by Adrianus Warmenhoven

Notes and References

1. Book: Knuth, Donald E. . The Art of Computer Programming, Volume 3: Sorting and Searching . 2nd . 1998 . Addison–Wesley . Reading, Massachusetts . 422 . 0-201-89685-0.