Uniform binary search: Difference between revisions

Content deleted Content added
No edit summary
Tags: Mobile edit Mobile web edit
m Disambiguating links to Mix (link changed to MIX (abstract machine)) using DisamAssist.
 
(One intermediate revision by one other user not shown)
Line 1:
'''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 (abstract machine)|MIX]]) on which
 
*a table lookup is generally faster than an addition and a shift, and
Line 7:
The uniform [[binary search algorithm]] looks like this, when implemented in [[C (programming language)|C]].
<!-- Please don't break this code. Test before editing! -->
<sourcesyntaxhighlight lang="c">
#define LOG_N 4
 
Line 58:
return 0;
}
</syntaxhighlight>
</source>
 
==References==