Uniform binary search
Encyclopedia
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
.
#define LOG_N 42
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]) {
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 i, a[N] = {1,3,5,6,7,9,14,15,17,19};
make_delta(N);
for (i=0; i < 20; ++i)
printf("%d is at index %d\n", i, unisearch(a, i));
return 0;
}
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
and given in Knuth's The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....
. It uses a lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
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
MIX
MIX is a hypothetical computer used in Donald Knuth's monograph, The Art of Computer Programming . MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machines deemed significant by the author...
) 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 CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
.
#define LOG_N 42
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 i, a[N] = {1,3,5,6,7,9,14,15,17,19};
make_delta(N);
for (i=0; i < 20; ++i)
printf("%d is at index %d\n", i, unisearch(a, i));
return 0;
}
External links
- An implementation of Knuth's algorithm in PascalPascal (programming language)Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
, by Han de Bruijn