Uniform binary search: Difference between revisions

Revision as of 07:41, 4 July 2016

Revision as of 03:41, 21 September 2017

Line 1:

{{Orphan|date=February 2009}}

'''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

'''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