Uniform binary search: Difference between revisions

Revision as of 00:54, 8 December 2006

Latest revision as of 10:09, 9 January 2024

(22 intermediate revisions by 16 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 424

static int delta[LOG_N];

#define LOG_N 42

void make_delta(int N)

static int delta[LOG_N];

{

int power = 1;

void make_delta(int N)

int di = 0;

{

int power = 1;

do int i = 0;{

do { int half = power;

power int half <<= power1;

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

} while (delta[i++] != (N + half0) / power;

}

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

}

int unisearch(int *a, int key)

{

int unisearch(int *a, int key)

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

{

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

int d = 0;

while (1) {

while if (1key == a[i]) {

if (key == a[i]) return i;

} else if (delta[d] == 0) return -1;{

else { return -1;

} else {

if (key < a[i]) i -= delta[++d];

if else(key i< += deltaa[++di];) {

} i -= delta[++d];

} else {

if (key < a[i]) i -+= delta[++d];

}

}

}

/* Example of use: */

}

#define N 10

}

int main(void)

{

/* Example of use: */

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

#define N 10

make_delta(N);

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

int main(void)

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

{

return 0;

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>

==References==

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

==External linklinks==

*[httphttps://huizengithub.dto.tudelft.nlcom/adrianuswarmenhoven/uniformbinarysearch_go/blob/deBruijnmaster/knuthPascal/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]]