Uniform binary search: Difference between revisions

Revision as of 03:42, 21 September 2017

Revision as of 03:42, 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 KnTheKnuth's ''[[The Art of Computer Programming]]''. ItusesIt 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 KnThe Art of Computer Programming]]''. 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