Uniform binary search: Difference between revisions

Revision as of 13:47, 24 June 2006

Latest revision as of 10:09, 9 January 2024

(27 intermediate revisions by 19 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 5:

==C implementation==

The uniform [[binary search algorithm]] looks like this, when implemented in [[C (programming language)|C]]:.

<!-- Please don't break this code. Test before editing! -->

<syntaxhighlight lang="c">

#define LOG_N 4

static int delta[LOG_N];

#define LOG_N 42

static int delta[LOG_N];

void make_delta(int N)

{

int lgN, power;

int i;

lgN = 0;

for (i = N; i > 0; i >>= 1)

++lgN;

power = 1;

for (i=0; i <= lgN; ++i) {

int half = power;

power <<= 1;

delta[i] = (N + half) / power;

}

}

int unisearch(int *a, int key)

{

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

int d = 0;

while (1) {

if (key == a[i]) {

return i;

}

if (delta[d] == 0) {

return -1;

}

if (key < a[i]) {

i -= delta[d++];

}

else {

i += delta[d++];

}

}

}

void mainmake_delta(voidint N)

{

int searchArray[]power = { 0, 2, 5, 9, 11, 15, 1;

int i = 0;

22, 24, 25, 29, 30, 31,

40, 45, 50, 55, 60 };

int saSize = sizeof(searchArray) / sizeof(searchArray[0]);

printf("saSize: %d\n", saSize);

make_delta(saSize - 2); // doesn't work unless subtract 2 ???

int index = unisearch(searchArray, 29);

index = unisearch(searchArray, 12);

index = unisearch(searchArray, 9);

index = unisearch(searchArray, 30);

for (int key = 0; key < 66; key += 3) {

index = unisearch(searchArray, key);

printf("Index: %-2d Key: %-2d Value: %-2d\n",

index, key, searchArray[index]);

}

}

do {

The programmer is expected to call <code>make_delta(N)</code> before attempting to use <code>unisearch(a, x)</code> on any array <code>a</code> with length <code>N</code>, and re-invoke <code>make_delta</code> before any call to <code>unisearch(b, x)</code> in which <code>b</code> has a different number of elements from <code>a</code>.

int half = power;

power <<= 1;

delta[i] = (N + half) / power;

} while (delta[i++] != 0);

}

int unisearch(int *a, int key)

The <code>make_delta</code> function initializes the array <code>delta</code> with successive halvings of <code>N</code>, rounded up; for example, if <code>N=40</code>, then <code>delta</code> will be initialized to {20, 10, 5, 3, 1, 1, 0}.

{

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

int d = 0;

while (1) {

--[[User:L d allan|Lynn]] 07:52, 24 June 2006 (UTC) Note that this code has a tough time with arrays that have an even number of elements ... I found you need to put 'sentinel' entries that are max-value at the end. I suspect the code wasn't translated quite right from the original MIX code in Dr. Knuth's book.

if (key == a[i]) {

return i;

} else if (delta[d] == 0) {

return -1;

} else {

if (key < a[i]) {

i -= delta[++d];

} else {

i += delta[++d];

}

}

}

}

/* Example of use: */

#define N 10

int main(void)

{

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

==References==

*[[Donald Knuth|Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3. Page 412, Algorithm C.

==External linklinks==

*[httphttps://huizengithub.dto.tudelft.nlcom/deBruijnadrianuswarmenhoven/knuthuniformbinarysearch_go/blob/master/Pascal/unizoek.pas An implementation of Knuth's algorithm] in [[Pascal (programming language)|Pascal]], by Han de Bruijn

*[https://github.com/adrianuswarmenhoven/uniformbinarysearch_go An implementation of Knuth's algorithm] in [[Go (programming language)|Go]], by [[:nl:Adrianus_Warmenhoven|Adrianus Warmenhoven]]

[[Category:Search algorithms]]

[[Category:Articles with example C code]]