Uniform binary search: Difference between revisions

Revision as of 15:52, 2 July 2020

Latest revision as of 10:09, 9 January 2024

(3 intermediate revisions by 2 users 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 16:

int power = 1;

int i = 0;

do {

int half = power;

Line 25 ⟶ 26:

int unisearch(int *a, int key)

{

int i = delta[0] - 1; /* midpoint of array */

int d = 0;

Line 45 ⟶ 46:

/* Example of use: */

#define N 10

int main(void)

{

int i, a[N] = {1, 3, 5, 6, 7, 9, 14, 15, 17, 19};

make_delta(N);

for (int i = 0; i < 20; ++i)

printf("%d is at index %d\n", i, unisearch(a, i));

return 0;

}

</syntaxhighlight>

</source>

==References==