Uniform binary search: Difference between revisions

Revision as of 18:42, 22 June 2016

Latest revision as of 10:09, 9 January 2024

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

{{Orphan|date=February 2009}}

'''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]]) on which

*a table lookup is generally faster than an addition and a shift, and

Line 8 ⟶ 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! -->

<syntaxhighlight lang="c">

#define LOG_N 4

static int delta[LOG_N];

#define LOG_N 4

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] == return0) i;{

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

} else return -1;{

} else if (key < a[i]) {

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

} else {
i -+= delta[++d];

} else {

i += delta[++d];}

}

}

}

}

/* Example of use: */

}

#define N 10

/* Example of use: */

int main(void)

#define N 10

{

int main(void)

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

{

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

make_delta(N);

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

for (int i = 0; i < 20; ++i)
printf("%d is at index %d\n", i, unisearch(a, i));

return 0;

}

</syntaxhighlight>

==References==

Line 60 ⟶ 65:

==External links==

*[https://github.com/adrianuswarmenhoven/uniformbinarysearch_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]]