Uniform binary search: Difference between revisions

Revision as of 02:50, 27 September 2006

Latest revision as of 10:09, 9 January 2024

(25 intermediate revisions by 17 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

*many searches will be performed on the same array, or on several arrays of the same length

==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];

void make_delta(int N)

{

int power = 1;

int i = 0;

do {

int half = power;

power <<= 1;

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

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

}

int unisearch(int *a, int key)

{

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

int d = 0;

while (1) {

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/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]]

[[Category:Articles with example C code]]