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
References
- Knuth. The Art of Computer Programming, Volume 3. Page 412, Algorithm C.
External link
- An implementation of Knuth's algorithm in Pascal, by Han de Bruijn