Uniform binary search: Difference between revisions

Revision as of 03:41, 21 September 2017

Revision as of 03:42, 21 September 2017

Line 1:

'''Uniform binary search''' is an optimization of the classic [[binary search]] algorithm invented by [[Donald Knuth]] and given in Knuth's ''[[TheKnThe Art of Computer Programming]]''. It uses a Ituses[[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

*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