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
The uniform binary search algorithm looks like this, when implemented in C.
#define LOG_N 4
static int deltaLOG_N];
void make_delta(int N)
{
int power = 1;
int i = 0;
do {
int half = power;
power <<= 1;
deltai = (N + half) / power;
} while (deltai++ != 0);
}
int unisearch(int *a, int key)
{
int i = delta0 - 1; /* midpoint of array */
int d = 0;
while (1) {
if (key == ai]) {
return i;
} else if (deltad == 0) {
return -1;
} else {
if (key < ai]) {
i -= delta++d];
} else {
i += delta++d];
}
}
}
}
/* Example of use: */
#define N 10
int main(void)
{
int aN = {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;
}
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
The uniform binary search algorithm looks like this, when implemented in C.
#define LOG_N 4
static int deltaLOG_N];
void make_delta(int N)
{
int power = 1;
int i = 0;
do {
int half = power;
power <<= 1;
deltai = (N + half) / power;
} while (deltai++ != 0);
}
int unisearch(int *a, int key)
{
int i = delta0 - 1; /* midpoint of array */
int d = 0;
while (1) {
if (key == ai]) {
return i;
} else if (deltad == 0) {
return -1;
} else {
if (key < ai]) {
i -= delta++d];
} else {
i += delta++d];
}
}
}
}
/* Example of use: */
#define N 10
int main(void)
{
int aN = {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;
}